choose a random element from a sequence of unknown length

vijayan121 0 764 Views

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

Dani AI

Generated

Nice, this is the standard one-pass solution known as "reservoir sampling" (single-sample case). 's sketch and example show the idea; below are a concise correctness sketch, practical cautions, and a short, safe generalization for selecting k items.

Correctness (brief): prove by induction. Base: first item is chosen with probability 1. Assume after seeing i-1 items each has probability 1/(i-1). When the i-th item arrives it is chosen with probability 1/i; any earlier item survives that step with probability 1 - 1/i. So an earlier item’s final probability becomes (1/(i-1)) * (1 - 1/i) = 1/i. That keeps all i items equally likely.

Practical notes and pitfalls:

  • RNG quality and bias: avoid using plain rand() % n for the uniform test if you need strict correctness — modulo can introduce bias when the RNG range is not a multiple of n. Prefer unbiased integer sampling (e.g., arc4random_uniform where available, or std::uniform_int_distribution with std::mt19937 in C++).
  • Counters: use a 64-bit counter (e.g., uint64_t or size_t) if the stream might be very large; 32-bit int can overflow.
  • Threading and determinism: rand() is not thread-safe. Use thread-local RNGs for concurrent code or pass an RNG object in.
  • Empty stream: handle and document the empty-stream result (NULL/sentinel).
  • If the selected element may be freed later, copy the value you need rather than returning a pointer to ephemeral storage.

Generalization (reservoir of size k):

reservoir = first k items
i = k
for each next item:
  i = i + 1
  j = uniform_int(0, i-1)
  if j < k: reservoir[j] = item

Complexity: single pass, O(n) time, O(1) extra space for k=1 (O(k) for general k). For very large streams where RNG calls are expensive, look into Vitter-style reservoir algorithms that skip items to reduce random draws.

Be a part of the DaniWeb community

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

Edit Preview