choose a random element from a sequence of unknown length UserPageVisits:585 active 80 80 DaniWeb 561 60 2007-04-29T23:20:46+00:00 https://www.daniweb.com/programming/software-development/code/216918/choose-a-random-element-from-a-sequence-of-unknown-length

choose a random element from a sequence of unknown length

vijayan121

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

585 Views
About the Author
code snippet
// 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 ;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.