Report a bug
If you spot a problem with this page, click here to create a Github issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

mir.random.algorithm

Authors:
Ilya Yaroshenko, documentation is partially based on Phobos.
struct RandomRange(G) if (isSaturatedRandomEngine!G);

RandomRange!G range(G)(ref G gen)
if (isSaturatedRandomEngine!G);
Range interface for uniform random bit generators.

Note: The structure holds a pointer to a generator. The structure must not be copied (explicitly or implicitly) outside from a function.

Examples:
import std.range, std.algorithm;
import mir.random.engine.xorshift;
auto rng = Xorshift(1);
auto bitSample = rng // by reference
    .range
    .filter!(val => val % 2 == 0)
    .map!(val => val % 100)
    .take(5)
    .array;
assert(bitSample == [58, 30, 86, 16, 76]);
enum ReturnType!G max;
Largest generated value.
this(ref G gen);
Constructor. Stores the pointer to the gen engine.
enum auto empty;

@property ReturnType!G front();

void popFront();
Infinity Input Range primitives
struct RandomRange(G, D) if (isSaturatedRandomEngine!G);

RandomRange!(G, D) range(G, D)(ref G gen, D var)
if (isSaturatedRandomEngine!G);
Range interface for random variables.

Note: The structure hold a pointer to a generator. The structure must not be copied (explicitly or implicitly) outside from a function.

Examples:
import std.range : take, array;

import mir.random;
import mir.random.variable: NormalVariable;

auto rng = Random(unpredictableSeed);
auto sample = rng // by reference
    .range(NormalVariable!double(0, 1))
    .take(1000)
    .array;

//import std.stdio;
//writeln(sample);
this(ref G gen, D var);
Constructor. Stores the pointer to the gen engine.
enum auto empty;

@property auto front();

void popFront();
Infinity Input Range primitives
struct VitterStrides;
Random sampling utility.

Complexity: O(n)

References: Jeffrey Scott Vitter, An efficient algorithm for sequential random sampling

Examples:
import mir.random.engine.xorshift;
auto gen = Xorshift(112);
auto strides = VitterStrides(20, 3);
size_t s;
foreach(_; 0..3)
{
    s += strides(gen) + 1;
    assert(s + strides.tail == 20);
}
this(size_t N, size_t n);
Parameters:
size_t N range length
size_t n sample length
@property bool empty();
Returns:
true if sample length equals to 0.
@property size_t length();
Returns:
N (remaining sample length)
@property size_t tail();
Returns:
n (remaining range length)
sizediff_t opCall(G)(ref G gen);
Returns:
random stride step (S). After each call N decreases by S + 1 and n decreases by 1.
Parameters:
G gen random number engine to use
auto sample(Range, G)(Range range, ref G gen, size_t n)
if (isInputRange!Range && hasLength!Range && isSaturatedRandomEngine!G);
Selects a random subsample out of range, containing exactly n elements. The order of elements is the same as in the original range.
Returns:
RandomSample over the range.
Parameters:
Range range range to sample from
G gen random number engine to use
size_t n number of elements to include in the sample; must be less than or equal to the range.length

Complexity: O(n)

Examples:
import std.range;
import mir.random.engine.xorshift;
auto gen = Xorshift(112);
auto sample = iota(100).sample(gen, 7);
foreach(elem; sample)
{
    //import std.stdio;
    //writeln(elem);
}
struct RandomSample(Range, G);
Lazy input or forward range containing a random sample. VitterStrides is used to skip elements.

Complexity: O(n)

Note: The structure holds a pointer to a generator. The structure must not be copied (explicitly or implicitly) outside from a function.

this(Range range, ref G gen, size_t n);
@property size_t length();

@property bool empty();

@property ref auto front();

void popFront();

@property auto save();
Range primitives
void shuffle(Range, G)(ref G gen, Range range)
if (isSaturatedRandomEngine!G && isRandomAccessRange!Range && hasLength!Range);
Shuffles elements of range.
Parameters:
G gen random number engine to use
Range range random-access range whose elements are to be shuffled

Complexity: O(range.length)

Examples:
import std.experimental.ndslice;
import std.algorithm.sorting;

auto gen = Random(unpredictableSeed);
auto a = iotaSlice(10).slice;

gen.shuffle(a);

sort(a);
assert(a == iotaSlice(10));
void shuffle(Range, G)(ref G gen, Range range, size_t n)
if (isSaturatedRandomEngine!G && isRandomAccessRange!Range && hasLength!Range);
Partially shuffles the elements of range such that upon returning range[0..n] is a random subset of range and is randomly ordered. range[n..r.length] will contain the elements not in range[0..n]. These will be in an undefined order, but will not be random in the sense that their order after shuffle returns will not be independent of their order before shuffle was called.
Parameters:
G gen random number engine to use
Range range random-access range with length whose elements are to be shuffled
size_t n number of elements of r to shuffle (counting from the beginning); must be less than r.length

Complexity: O(n)

Examples:
import std.experimental.ndslice;
import std.algorithm.sorting;

auto gen = Random(unpredictableSeed);
auto a = iotaSlice(10).slice;

gen.shuffle(a, 4);

sort(a);
assert(a == iotaSlice(10));