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