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