Reservoir Sampling Algorithm

Returns an array R containing k distinct elements picked randomly from an array A of size n so that all possible samples are equiprobable.

Require: array A made of n elements indexed from 0 to n − 1  
Require: integer k (0 < k ≤ n)  
 
1: R ← array of size k  
2: for i = 0, ... , k − 1 do  
3:     R[i] ← A[i]  
4: end for  
5: for i = k, ... , n − 1 do  
6:     j ← random integer in [0, i]  
7:     if j < k then  
8:         R[j] ← A[i]  
9:     end if  
10: end for  
11: return R