randomShuffle

[Joseph Rushton Wakeling]

On 06/03/2013 02:30 PM, Joseph Rushton Wakeling wrote:
> On 06/03/2013 01:29 PM, Diggory wrote:
>> For small samples from very large ranges an efficient algorithm would be:
>>
>> int[] randomGen(int N, int M) {
>>     if (N == 0)
>>         return [];
>>
>>     int[] result = randomGen(N-1, M-1);
>>
>>     int num = rand(M);
>>     foreach (ref int i; result)
>>         if (i >= num)
>>             ++i;
>>
>>     result ~= num;
>>
>>     return result;
>> }
> 
> Are you sure about the efficiency of that algorithm?  Looks like it's be O(M) to me.
> 
> randomSample currently has a computational complexity (and number of random
> numbers required) of O(n) where n is sample size.

There are at least two other key faults with that algorithm compared to
randomSample -- you're alloc'ing repeatedly inside it, and you return the whole
sample.  randomSample doesn't require any such storage, it can take any input
range as the sample source and just jumps across the range; and what it returns
is another range interface, from which you can take the sample points sequentially.