randomSample

[Andrei Alexandrescu]

Jason House wrote:
> Andrei Alexandrescu Wrote:
> 
>> 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
> 
> You have your probability wrong. The selection probability is k/n.
> Pick a number in [0,n) and pick the element if the result is in
> [0,k). If you do select an item, decrement k. Always decrement n when
> popping, regardless of if the element is selected.

Great, thanks, that works perfect. If I want to choose _toSelect stuff 
out of _available items, this works to position to the next element:

         for (;;)
         {
             auto r = uniform(0, _available);
             if (r < _toSelect)
             {
                 // chosen!
                 return;
             }
             // not chosen, retry
             assert(!_input.empty);
             _input.popFront;
             --_available;
             assert(_available > 0);
         }

As an aside, it looks like the right-open range for random numbers is a 
good default.


Andrei