mir.combinatorics

import mir.ndslice.fuse;

assert(['a', 'b'].permutations.fuse == [['a', 'b'], ['b', 'a']]);
assert(['a', 'b'].cartesianPower(2).fuse == [['a', 'a'], ['a', 'b'], ['b', 'a'], ['b', 'b']]);
assert(['a', 'b'].combinations(2).fuse == [['a', 'b']]);
assert(['a', 'b'].combinationsRepeat(2).fuse == [['a', 'a'], ['a', 'b'], ['b', 'b']]);

assert(permutations!ushort(2).fuse == [[0, 1], [1, 0]]);
assert(cartesianPower!ushort(2, 2).fuse == [[0, 0], [0, 1], [1, 0], [1, 1]]);
assert(combinations!ushort(2, 2).fuse == [[0, 1]]);
assert(combinationsRepeat!ushort(2, 2).fuse == [[0, 0], [0, 1], [1, 1]]);

assert([3, 1].permutations!ubyte.fuse == [[3, 1], [1, 3]]);
assert([3, 1].cartesianPower!ubyte(2).fuse == [[3, 3], [3, 1], [1, 3], [1, 1]]);
assert([3, 1].combinations!ubyte(2).fuse == [[3, 1]]);
assert([3, 1].combinationsRepeat!ubyte(2).fuse == [[3, 3], [3, 1], [1, 1]]);

R binomial(R = ulong, T)(T n, T k)
if (isArithmetic!(R, T) && (is(typeof(T.min < 0)) && is(typeof(T.init & 1)) || !is(typeof(T.min < 0))));

Computes the binomial coefficient of n and k. It is also known as "n choose k" or more formally as _n!/_k!(_n-_k). If a fixed-length integer type is used and an overflow happens, 0 is returned.

Uses the generalized binomial coefficient for negative integers and floating point number

Parameters:

T n	arbitrary arithmetic type
T k	arbitrary arithmetic type

Returns:

Binomial coefficient

Examples:

assert(binomial(5, 2) == 10);
assert(binomial(6, 4) == 15);
assert(binomial(3, 1) == 3);

import std.bigint: BigInt;
assert(binomial!BigInt(1000, 10) == BigInt("263409560461970212832400"));

IndexedRoR!(Collection, Range) indexedRoR(Collection, Range)(Collection collection, Range range)
if (__traits(compiles, Range.init[size_t.init]));

struct IndexedRoR(Collection, Range) if (__traits(compiles, Range.init[size_t.init]));

Creates a projection of a generalized Collection range for the numeric case case starting from 0 onto a custom range of any type.

Parameters:

Collection collection	range to be projected from
Range range	random access range to be projected to

Returns:

Range with a projection to range for every element of collection

See Also:

permutations, cartesianPower, combinations, combinationsRepeat

Examples:

import mir.ndslice.fuse;

auto perms = 2.permutations;
assert(perms.save.fuse == [[0, 1], [1, 0]]);

auto projection = perms.indexedRoR([1, 2]);
assert(projection.fuse == [[1, 2], [2, 1]]);

Examples:

import mir.ndslice.fuse;
// import mir.ndslice.topology: only;

auto projectionD = 2.permutations.indexedRoR("ab"d);
assert(projectionD.fuse == [['a', 'b'], ['b', 'a']]);

// auto projectionC = 2.permutations.indexedRoR(only('a', 'b'));
// assert(projectionC.fuse == [['a', 'b'], ['b', 'a']]);

pure nothrow @safe Permutations!T permutations(T = uint)(size_t n)
if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

pure nothrow @safe IndexedRoR!(Permutations!T, Range) permutations(T = uint, Range)(Range r)
if (__traits(compiles, Range.init[size_t.init]));

Permutations!T makePermutations(T = uint, Allocator)(auto ref Allocator alloc, size_t n)
if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

Lazily computes all permutations of r using Heap's algorithm.

While generating a new item is in O(k) (amortized O(1)), the number of permutations is |n|!.

Parameters:

size_t n	number of elements (|r|)
Range r	random access field. A field may not have iteration primitivies.
Allocator alloc	custom Allocator

Returns:

Forward range, which yields the permutations

See Also:

Permutations

struct Permutations(T) if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

Lazy Forward range of permutations using Heap's algorithm.

It always generates the permutations from 0 to n - 1, use indexedRoR to map it to your range.

Generating a new item is in O(k) (amortized O(1)), the total number of elements is n^k.

See Also:

permutations, makePermutations

Examples:

import mir.ndslice.fuse;
import mir.ndslice.topology : iota;

auto expectedRes = [[0, 1, 2],
     [1, 0, 2],
     [2, 0, 1],
     [0, 2, 1],
     [1, 2, 0],
     [2, 1, 0]];

auto r = iota(3);
auto rp = permutations(r.length).indexedRoR(r);
assert(rp.fuse == expectedRes);

// direct style
auto rp2 = iota(3).permutations;
assert(rp2.fuse == expectedRes);

Examples:

import mir.algorithm.iteration: equal;
import mir.ndslice.slice: sliced;
import mir.ndslice.topology : iota;

import std.experimental.allocator.mallocator;

static immutable expected2 = [0, 1, 1, 0];
auto r = iota(2);
auto rp = makePermutations(Mallocator.instance, r.length);
assert(expected2.sliced(2, 2).equal(rp.indexedRoR(r)));
dispose(Mallocator.instance, rp);

alias DeepElement = T;

pure nothrow @nogc @safe this()(T[] state, T[] indices);

state should have the length of n - 1, whereas the length of indices should be n

pure nothrow @nogc @property @safe Slice!(const(T)*) front()();

pure nothrow @nogc scope @safe void popFront()();

const pure nothrow @nogc @property scope @safe bool empty()();

const pure nothrow @nogc @property scope @safe size_t length()();

Input range primitives

const @property scope size_t[2] shape()();

pure nothrow @property @safe Permutations save()();

Forward range primitive. Allocates using GC.

void dispose(T, Allocator)(auto ref Allocator alloc, auto ref Permutations!T perm);

Disposes a Permutations object. It destroys and then deallocates the Permutations object pointed to by a pointer. It is assumed the respective entities had been allocated with the same allocator.

Parameters:

Allocator alloc	Custom allocator
Permutations!T perm	Permutations object

See Also:

makePermutations

pure nothrow @safe CartesianPower!T cartesianPower(T = uint)(size_t n, size_t repeat = 1)
if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

IndexedRoR!(CartesianPower!T, Range) cartesianPower(T = uint, Range)(Range r, size_t repeat = 1)
if (isUnsigned!T && __traits(compiles, Range.init[size_t.init]));

CartesianPower!T makeCartesianPower(T = uint, Allocator)(auto ref Allocator alloc, size_t n, size_t repeat)
if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

Lazily computes the Cartesian power of r with itself for a number of repetitions D repeat. If the input is sorted, the product is in lexicographic order.

While generating a new item is in O(k) (amortized O(1)), the total number of elements is n^k.

Parameters:

size_t n	number of elements (|r|)
Range r	random access field. A field may not have iteration primitivies.
size_t repeat	number of repetitions
Allocator alloc	custom Allocator

Returns:

Forward range, which yields the product items

See Also:

CartesianPower

struct CartesianPower(T) if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

Lazy Forward range of Cartesian Power. It always generates Cartesian Power from 0 to n - 1, use indexedRoR to map it to your range.

Generating a new item is in O(k) (amortized O(1)), the total number of elements is n^k.

See Also:

cartesianPower, makeCartesianPower

Examples:

import mir.ndslice.fuse;
import mir.ndslice.topology: iota;
assert(iota(2).cartesianPower.fuse == [[0], [1]]);
assert(iota(2).cartesianPower(2).fuse == [[0, 0], [0, 1], [1, 0], [1, 1]]);

auto three_nums_two_bins = [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]];
assert(iota(3).cartesianPower(2).fuse == three_nums_two_bins);

assert("AB"d.cartesianPower(2).fuse == ["AA"d, "AB"d, "BA"d, "BB"d]);

Examples:

import mir.ndslice.topology: iota;
import mir.algorithm.iteration: equal;
import mir.ndslice.slice: sliced;

import std.experimental.allocator.mallocator: Mallocator;
auto alloc = Mallocator.instance;

static immutable expected2r2 = [
    0, 0,
    0, 1,
    1, 0,
    1, 1];
auto r = iota(2);
auto rc = alloc.makeCartesianPower(r.length, 2);
assert(expected2r2.sliced(4, 2).equal(rc.indexedRoR(r)));
alloc.dispose(rc);

alias DeepElement = T;

pure nothrow @nogc @safe this()(size_t n, T[] state);

state should have the length of repeat

pure nothrow @nogc @property @safe Slice!(const(T)*) front()();

pure nothrow @nogc scope @safe void popFront()();

const pure nothrow @nogc @property scope @safe size_t length()();

const pure nothrow @nogc @property scope @safe bool empty()();

Input range primitives

const @property scope size_t[2] shape()();

pure nothrow @property @safe CartesianPower save()();

Forward range primitive. Allocates using GC.

void dispose(T = uint, Allocator)(auto ref Allocator alloc, auto ref CartesianPower!T cartesianPower);

Disposes a CartesianPower object. It destroys and then deallocates the CartesianPower object pointed to by a pointer. It is assumed the respective entities had been allocated with the same allocator.

Parameters:

Allocator alloc	Custom allocator
CartesianPower!T cartesianPower	CartesianPower object

See Also:

makeCartesianPower

pure nothrow @safe Combinations!T combinations(T = uint)(size_t n, size_t k = 1)
if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

IndexedRoR!(Combinations!T, Range) combinations(T = uint, Range)(Range r, size_t k = 1)
if (isUnsigned!T && __traits(compiles, Range.init[size_t.init]));

Combinations!T makeCombinations(T = uint, Allocator)(auto ref Allocator alloc, size_t n, size_t repeat)
if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

Lazily computes all k-combinations of r. Imagine this as the cartesianPower filtered for only strictly ordered items.

While generating a new combination is in O(k), the number of combinations is binomial(n, k).

Parameters:

size_t n	number of elements (|r|)
Range r	random access field. A field may not have iteration primitivies.
size_t k	number of combinations
Allocator alloc	custom Allocator

Returns:

Forward range, which yields the k-combinations items

See Also:

Combinations

struct Combinations(T) if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

Lazy Forward range of Combinations. It always generates combinations from 0 to n - 1, use indexedRoR to map it to your range.

Generating a new combination is in O(k), the number of combinations is binomial(n, k).

See Also:

combinations, makeCombinations

Examples:

import mir.ndslice.fuse;
import mir.ndslice.topology: iota;
assert(iota(3).combinations(2).fuse == [[0, 1], [0, 2], [1, 2]]);
assert("AB"d.combinations(2).fuse == ["AB"d]);
assert("ABC"d.combinations(2).fuse == ["AB"d, "AC"d, "BC"d]);

Examples:

import mir.algorithm.iteration: equal;
import mir.ndslice.slice: sliced;
import mir.ndslice.topology: iota;

import std.experimental.allocator.mallocator;
auto alloc = Mallocator.instance;

static immutable expected3r2 = [
    0, 1,
    0, 2,
    1, 2];
auto r = iota(3);
auto rc = alloc.makeCombinations(r.length, 2);
assert(expected3r2.sliced(3, 2).equal(rc.indexedRoR(r)));
alloc.dispose(rc);

alias DeepElement = T;

pure nothrow @nogc @safe this()(size_t n, T[] state);

state should have the length of repeat

pure nothrow @nogc @property @safe Slice!(const(T)*) front()();

pure nothrow @nogc scope @safe void popFront()();

const pure nothrow @nogc @property scope @safe size_t length()();

const pure nothrow @nogc @property scope @safe bool empty()();

Input range primitives

const @property scope size_t[2] shape()();

pure nothrow @property @safe Combinations save()();

Forward range primitive. Allocates using GC.

void dispose(T, Allocator)(auto ref Allocator alloc, auto ref Combinations!T perm);

Disposes a Combinations object. It destroys and then deallocates the Combinations object pointed to by a pointer. It is assumed the respective entities had been allocated with the same allocator.

Parameters:

Allocator alloc	Custom allocator
Combinations!T perm	Combinations object

See Also:

makeCombinations

pure nothrow @safe CombinationsRepeat!T combinationsRepeat(T = uint)(size_t n, size_t k = 1)
if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

IndexedRoR!(CombinationsRepeat!T, Range) combinationsRepeat(T = uint, Range)(Range r, size_t k = 1)
if (isUnsigned!T && __traits(compiles, Range.init[size_t.init]));

CombinationsRepeat!T makeCombinationsRepeat(T = uint, Allocator)(auto ref Allocator alloc, size_t n, size_t repeat)
if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

Lazily computes all k-combinations of r with repetitions. A k-combination with repetitions, or k-multicombination, or multisubset of size k from a set S is given by a sequence of k not necessarily distinct elements of S, where order is not taken into account. Imagine this as the cartesianPower filtered for only ordered items.

While generating a new combination with repeats is in O(k), the number of combinations with repeats is binomial(n + k - 1, k).

Parameters:

size_t n	number of elements (|r|)
Range r	random access field. A field may not have iteration primitivies.
size_t k	number of combinations
Allocator alloc	custom Allocator

Returns:

Forward range, which yields the k-multicombinations items

See Also:

CombinationsRepeat

struct CombinationsRepeat(T) if (isUnsigned!T && (T.sizeof <= size_t.sizeof));

Lazy Forward range of combinations with repeats. It always generates combinations with repeats from 0 to n - 1, use indexedRoR to map it to your range.

Generating a new combination with repeats is in O(k), the number of combinations with repeats is binomial(n, k).

See Also:

combinationsRepeat, makeCombinationsRepeat

Examples:

import mir.ndslice.fuse;
import mir.ndslice.topology: iota;

assert(iota(2).combinationsRepeat.fuse == [[0], [1]]);
assert(iota(2).combinationsRepeat(2).fuse == [[0, 0], [0, 1], [1, 1]]);
assert(iota(3).combinationsRepeat(2).fuse == [[0, 0], [0, 1], [0, 2], [1, 1], [1, 2], [2, 2]]);
assert("AB"d.combinationsRepeat(2).fuse == ["AA"d, "AB"d,  "BB"d]);

Examples:

import mir.algorithm.iteration: equal;
import mir.ndslice.slice: sliced;
import mir.ndslice.topology: iota;

import std.experimental.allocator.mallocator;
auto alloc = Mallocator.instance;

static immutable expected3r1 = [
    0, 
    1, 
    2];
auto r = iota(3);
auto rc = alloc.makeCombinationsRepeat(r.length, 1);
assert(expected3r1.sliced(3, 1).equal(rc.indexedRoR(r)));
alloc.dispose(rc);

alias DeepElement = T;

pure nothrow @nogc @safe this()(size_t n, T[] state);

state should have the length of repeat

pure nothrow @nogc @property @safe Slice!(const(T)*) front()();

pure nothrow @nogc scope @safe void popFront()();

const pure nothrow @nogc @property scope @safe size_t length()();

const pure nothrow @nogc @property scope @safe bool empty()();

Input range primitives

const @property scope size_t[2] shape()();

pure nothrow @property @safe CombinationsRepeat save()();

Forward range primitive. Allocates using GC.

void dispose(T, Allocator)(auto ref Allocator alloc, auto ref CombinationsRepeat!T perm);

Disposes a CombinationsRepeat object. It destroys and then deallocates the CombinationsRepeat object pointed to by a pointer. It is assumed the respective entities had been allocated with the same allocator.

Parameters:

Allocator alloc	Custom allocator
CombinationsRepeat!T perm	CombinationsRepeat object

See Also:

makeCombinationsRepeat