hap.random.adaptor

Implements algorithms that transform the output of uniform random number generators into other random behaviours, such as shuffling, sampling, and so on. Typically these are implemented as range objects that wrap a provided RNG instance.

As with the random number generators provided elsewhere in this package, the range objects implemented here are implemented as final classes to enforce reference semantics. They also assume that the RNGs they make use of have reference type semantics. User-supplied value-type RNGs may result in incorrect behaviour when used with these objects.

License:
Boost License 1.0.

Authors:
Andrei Alexandrescu, Joseph Rushton Wakeling

Source:
hap/random/adaptor.d

class Cover(Range, UniformRNG) if (isRandomAccessRange!Range && isUniformRNG!UniformRNG);
auto cover(Range, UniformRNG)(Range r, UniformRNG rng) if (isRandomAccessRange!Range && isUniformRNG!UniformRNG);
auto cover(Range)(Range r) if (isRandomAccessRange!Range);
alias randomCover = cover(Range, UniformRNG)(Range r, UniformRNG rng) if (isRandomAccessRange!Range && isUniformRNG!UniformRNG);
Covers a given range r in a random manner, i.e. goes through each element of r once and only once, but in a random order. r must be a random-access range with length.

If no random number generator is passed to cover, the thread-global RNG rndGen will be used as the source of randomness.

Example:
int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ];
foreach (e; cover(a))
{
    writeln(e);
}

// using a specified random number generator
auto gen = new Random(unpredictableSeed);
foreach (e; cover(a, gen))
{
    writeln(e);
}

The alias randomCover is available to ease migration for code written using std.random.randomCover.

const pure nothrow @property @safe bool empty();
const pure nothrow @property ref @safe auto front();
void popFront();
const pure nothrow @property @safe size_t length();
@property typeof(this) save();
Range primitives.

class Sample(Range, UniformRNG) if (isInputRange!Range && isUniformRNG!UniformRNG);
auto sample(Range)(Range r, size_t n, size_t total) if (isInputRange!Range);
auto sample(Range)(Range r, size_t n) if (isInputRange!Range && hasLength!Range);
auto sample(Range, UniformRNG)(Range r, size_t n, size_t total, UniformRNG rng) if (isInputRange!Range && isUniformRNG!UniformRNG);
auto sample(Range, UniformRNG)(Range r, size_t n, UniformRNG rng) if (isInputRange!Range && hasLength!Range && isUniformRNG!UniformRNG);
alias randomSample = sample(Range)(Range r, size_t n, size_t total) if (isInputRange!Range);
Selects a random subsample out of r, containing exactly n elements. The order of elements is the same as in the original range. The total length of r must be known. If total is passed in, the total number of elements available to sample is considered to be total. Otherwise, Sample uses r.length.

Sample implements Jeffrey Scott Vitter's Algorithm D (see Vitter 1984, 1987), which selects a sample of size n in O(n) steps and requiring O(n) random variates, regardless of the size of the data being sampled. The exception to this is if traversing k elements on the input range is itself an O(k) operation (e.g. when sampling lines from an input file), in which case the sampling calculation will inevitably be of O(total).

Sample will throw an error if total is verifiably less than the total number of elements available in the input, or if n > total.

If no random number generator is passed to sample, the thread-local default RNG rndGen will be used as the source of randomness.

Example:
int[] arr = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
// Print 5 random elements picked from arr
foreach (e; sample(arr, 5))
{
    writeln(e);
}

// Print 5 random elements picked from arr,
// using a specified random number generator
auto gen = new Random(unpredictableSeed);
foreach (e; sample(arr, 5, gen))
{
    writeln(e);
}

The alias randomSample is available to ease migration for code written using std.random.randomSample.

const pure nothrow @property @safe bool empty();
@property ref auto front();
void popFront();
@property typeof(this) save();
const pure nothrow @property @safe size_t length();
Range primitives.

size_t index();
Returns the index of the visited record.

auto shuffle(Range, UniformRNG)(Range r, UniformRNG gen) if (isRandomAccessRange!Range && isUniformRNG!UniformRNG);
auto shuffle(Range)(Range r) if (isRandomAccessRange!Range);
alias randomShuffle = shuffle(Range, UniformRNG)(Range r, UniformRNG gen) if (isRandomAccessRange!Range && isUniformRNG!UniformRNG);
Shuffles elements of r using gen as a shuffler. r must be a random-access range with length. If no RNG is specified, rndGen will be used. Returns the newly-shuffled range, and so is composable:

Example:
// generates the array [0, 1, ..., 10],
// shuffles it, and writes to console
iota(10).array.shuffle.writeln;

A randomShuffle alias has been provided to ease migration from code written using std.random.randomShuffle.

auto partialShuffle(Range, UniformRNG)(Range r, in size_t n, UniformRNG gen) if (isRandomAccessRange!Range && isUniformRNG!UniformRNG);
auto partialShuffle(Range)(Range r, in size_t n) if (isRandomAccessRange!Range);
Partially shuffles the elements of r such that upon returning r[0..n] is a random subset of r and is randomly ordered. r[n..r.length] will contain the elements not in r[0..n]. These will be in an undefined order, but will not be random in the sense that their order after partialShuffle returns will not be independent of their order before partialShuffle was called.

r must be a random-access range with length. n must be less than or equal to r.length. If no RNG is specified, rndGen will be used.