struct node { int key; struct node* next; }; void printRandom(struct node *head)
ID: 3694541 • Letter: S
Question
struct node
{
int key;
struct node* next;
};
void printRandom(struct node *head)
{
if (head == NULL)
return;
int result = head->key;
struct node *current = head;
int n;
for (n=2; current!=NULL; n++)
{
if (rand() % n == 0)
result = current->key;
current = current->next;
}
printf("Randomly key is %d ", result);
}
How can I use the code above to print out the probability each node has of getting chosen? I'd like each node to have the same probability of getting chosen (in linked list form at the moment)
Explanation / Answer
The probality of choosing head = 1/2 (Because rand()%2 is 0 with probability 1/2)
The probality of choosing head->next = 1/2*1/3=1/6 ( Because rand()%3 is 0 with probability 1/3 and probability that head node is not selected is 1/2).
The probality of choosing head->next->next = 1/2*2/3*1/4=1/12
The probality of choosing head->next->next->next = 1/2*2/3*3/4*1/5=1/20
The probality of choosing head->next.....(ntimes) = 1/(n+1)(n+2)
To select nodes uniformly first find number of nodes in the linked list. Let it be n.
let k=rand()%n
struct node *current = head;
int i;
for (i=0; i<k; i++){
current = current->next;
}
return current;
This gives you a random node with uniform probability.
Example:
If you have 10 nodes in your linked list.
if rand()%10 produces 0 then you choose head.
if rand()%10 produces 1 then you choose head->next.
if rand()%10 produces 2 then you choose head->next->next.
.
.
.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.