Random sampling in Phobos

[Lars T. Kyllingstad]

On Wednesday, 18 April 2012 at 01:17:18 UTC, Joseph Rushton 
Wakeling wrote:
> On 17/04/12 18:25, Joseph Rushton Wakeling wrote:
>> On 17/04/12 17:31, Andrei Alexandrescu wrote:
>>> Actually that's not correct. RandomSample works fine with an 
>>> input range and
>>> does not keep it in memory.
>>
>> Ahh, OK. I should have anticipated this as the output also 
>> works as a range.
>
> A query on this point, as it looks like this can have some 
> unfortunate side-effects.
>
> If I write e.g.
>
>     auto s = randomSample(iota(0,100), 5);
>
>     foreach(uint i; s)
>         writeln(i);
>
>     writeln();
>
>     foreach(uint i; s)
>         writeln(i);
>
> ... then it's noticeable that the _first_ element of the two 
> sample lists is identical, while the others change.  If I put 
> in place a specified source of randomness, e.g.
>
>     auto s = randomSample(iota(0,100), 5, rndGen);
>
> ... then the numbers stay the same for both lists.
>
> I'm presuming that the first element remains identical because 
> it's defined in the constructor rather than elsewhere, but it's 
> not clear why passing a defined RNG produces identical output 
> on both occasions.
>
> The effect can be worse with Vitter's Algorithm D because 
> often, having defined the first element, the second may be 
> derived deterministically -- meaning the first 2 elements of 
> the sample are identical.
>
> I'm sure that the above use of the RandomSample struct is not 
> the advised use, but it's still disconcerting to see this.

I've run into this trap more than once. :)  You have to pass the 
random number generator by ref, otherwise you are just generating 
two identical sequences of random numbers.  Just change the 
randomSample signature to:

     auto randomSampleVitter(R, Random)(R r, size_t n, ref Random 
gen)

-Lars