randomSample

[Andrei Alexandrescu]

I'm writing a range to select a random sampling of a forward range. The 
number of elements in the forward range is already known.

The strategy is: at any moment, I know I need to select k random samples 
out of n. To implement popFront, I generate a random number in [0, n - 
k]. That's the probability that the next item in the input will be part 
of the selection. If the random number is 0, then the element got 
selected. Otherwise, I must ignore that guy so I popFront the input 
range, decrease n by one, and repeat.

This seems reasonable but somehow the selection comes skewed: the 
elements towards the beginning of the range are less represented than 
the ones towards the end. Where am I wrong?


Andrei