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

```
// 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 ;
}
```

About the Author