Report a bug
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.combinatorics

This module contains various combinatorics algorithms.
Authors:
Sebastian Wilzbach, Ilya Yaroshenko
Examples:
```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
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
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.
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 `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
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
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.
Examples:
```import mir.ndslice.fuse;
import mir.ndslice.topology: iota;
assert(iota(2).cartesianPower.fuse == [, ]);
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 `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
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
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).
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 `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
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
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).
Examples:
```import mir.ndslice.fuse;
import mir.ndslice.topology: iota;

assert(iota(2).combinationsRepeat.fuse == [, ]);
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 `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