```
// to choose a random element from a sequence when
// a. you do not know how many elements are there before hand
// b. you want to make one single pass through the sequence
// c. you do not want to use auxiliary storage
// algorithm:
// step 1: select first element with probability 1
// step 2: replace the first element with the second with probability 1/2
// now both first and second are equally likely (prob 1/2 each)
// step 3: replace the selected with the third with probability 1/3
// now first, second and third are equally likely (prob 1/3 each)
// .....
// step n: replace the selected element with the nth with probability 1/n
// now any of the n are equally likely (prob 1/n each)
// continue till end of sequence
// note: this algorithm (with appropriate modifications) can be used in
// a. reading a random line from a file
// b. filling up an array with unique random values
// c. generating n random values in ascending order
// and so on.
//
// here is a C implementation
// to choose a random node from a singly linked list
#include <stdlib.h>
typedef struct node node ;
struct node { int value ; node* next ; };
node* choose_random_node( node* first )
{
int num_nodes = 0 ; // nodes seen so far
node* selected = NULL ; // selected node
node* pn = NULL ;
for( pn = first ; pn != NULL ; pn = pn->next )
if( ( rand() % ++num_nodes ) == 0 ) selected = pn ;
return selected ;
}
```

1

Contributor0

Replies2

Views**Are you able to help answer this sponsored question?**

Questions asked by members who have earned a lot of community kudos are featured in order to give back and encourage quality replies.

Recommended Articles