std.random

[Denis Koroskin]

On Sat, 10 Jan 2009 07:12:13 +0300, yes <yes at no.com> wrote:

>
> How do I use this?
> I'd like a fast shuffle of a large array.
>
> void randomShuffle(T, SomeRandomGen)(T[] array, ref SomeRandomGen r);
> Shuffles elements of array using r as a shuffler.
>
> Shuffling a whole array should be faster than taking a random element  
> every time and keeping track of taken elements, right?

Shuffling is usually implemented in-place. A random element is picked, swapped with last one, and then range is decreased. Something like this:

void shuffle(T)(T[] array)
{
    int len = array.length;
    while (len > 1) {
	int offset = random(0, len); // get a random value that belongs to [0, len)
        --len;
        swap(array[offset], array[len]);
        array.length = len;
    }
}

The algorithm is very simple. However, user might not be satisfied with "default" distribution and thus be able to provide his own random number generator. That's what "SomeRandomGen" object is needed for.