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

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