randomShuffle

[Joseph Rushton Wakeling]

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.