randomShuffle

[Diggory]

On Monday, 3 June 2013 at 13:18:30 UTC, Joseph Rushton Wakeling 
wrote:
> 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.
>
> Apologies, I misread the algorithm slightly.  Your qualifier is 
> quite correct --
> when the number of sample points is very small (e.g. 5 out of 
> some arbitrary
> very large number), that algorithm is very quick indeed (I ran 
> some tests as I
> was curious:-), and can outperform D's randomSample.
>
> It doesn't scale with the size of the input (your value M), but 
> with the number
> of sample points n, but that scaling is very bad -- so as the 
> sample size grows
> it becomes _much_ worse than randomSample.
>
> Do you have a reference for the algorithm?  Off the top of my 
> head I don't
> recognize it from any of the texts I've read.

Thanks for testing before dismissing completely :P The way it 
returns results can be improved a lot by pre-allocating a range 
of the necessary size/using a range passed in.

The complexity is O(N²) where N is the number of samples out of 
M. The algorithm is something I just thought of although I've 
possibly used it before and I'm sure someone else has thought of 
it too. It's quite simple, it effectively says "pick a value from 
the range except for this value" recursively but instead of 
dividing the range in two, it shifts the top part down first to 
make a contiguous range and then shifts the results which are 
past the split up one afterward.

I expect the phobos implementation to be something like O(M) in 
which case my method would be faster whenever N < sqrt(M) (with 
the optimisations)