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.combinatorics

This module contains various combinatorics algorithms.
Authors:
Sebastian Wilzbach, Ilya Yaroshenko
Examples:
import std.algorithm.comparison: equal;

assert([0, 1].permutations.equal!equal([[0, 1], [1, 0]]));
assert([0, 1].cartesianPower(2).equal!equal([[0, 0], [0, 1], [1, 0], [1, 1]]));
assert([0, 1].combinations(2).equal!equal([[0, 1]]));
assert([0, 1].combinationsRepeat(2).equal!equal([[0, 0], [0, 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 c, Range r)
if (isRandomAccessRange!Range);

struct IndexedRoR(Collection, Range) if (isRandomAccessRange!Range);
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 range to be projected from
range random access range to be projected to
Returns:
Range with a projection to range for every element of collection
Examples:
import std.algorithm.comparison: equal;

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

auto projection = perms.indexedRoR([1, 2]);
assert(projection.equal!equal([[1, 2], [2, 1]]));
Examples:
import std.algorithm.comparison: equal;
import std.range: only;

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

auto projectionC = 2.permutations.indexedRoR(only('a', 'b'));
assert(projectionC.equal!equal([['a', 'b'], ['b', 'a']]));
pure nothrow @safe Permutations permutations(size_t n);

pure nothrow @safe IndexedRoR!(Permutations, Range) permutations(Range)(Range r)
if (isRandomAccessRange!Range);

Permutations makePermutations(Allocator)(auto ref Allocator alloc, size_t n);
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 range
Allocator alloc custom Allocator
Returns:
Forward range, which yields the permutations
See Also:
struct Permutations;
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 std.algorithm.comparison : equal;
import std.range : 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.equal!equal(expectedRes));

// direct style
auto rp2 = iota(3).permutations;
assert(rp2.equal!equal(expectedRes));
Examples:
import std.algorithm: equal;
import std.range : 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(rp.indexedRoR(r).equal!equal(expected2));
dispose(Mallocator.instance, rp);
pure nothrow @nogc @safe this(uint[] state, uint[] indices);
state should have the length of n - 1, whereas the length of indices should be n
pure nothrow @nogc @property @safe const(uint)[] front();
pure nothrow @nogc @safe void popFront();
const pure nothrow @nogc @property @safe bool empty();
const pure nothrow @nogc @property @safe size_t length();
pure nothrow @property @safe Permutations save();
void dispose(Allocator)(auto ref Allocator alloc, auto ref Permutations 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 perm Permutations object
pure nothrow @safe CartesianPower cartesianPower(size_t n, size_t repeat = 1);

IndexedRoR!(CartesianPower, Range) cartesianPower(Range)(Range r, size_t repeat = 1)
if (isRandomAccessRange!Range);

CartesianPower makeCartesianPower(Allocator)(auto ref Allocator alloc, size_t n, size_t repeat);
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 range
size_t repeat number of repetitions
Allocator alloc custom Allocator
Returns:
Forward range, which yields the product items
See Also:
struct CartesianPower;
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 std.algorithm: equal;
import std.range: iota;
assert(iota(2).cartesianPower.equal!equal([[0], [1]]));
assert(iota(2).cartesianPower(2).equal!equal([[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).equal!equal(three_nums_two_bins));

assert("AB"d.cartesianPower(2).equal!equal(["AA"d, "AB"d, "BA"d, "BB"d]));
Examples:
import std.algorithm: equal;
import std.range: iota;

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(rc.indexedRoR(r).equal!equal(expected2r2));
alloc.dispose(rc);
pure nothrow @nogc @safe this(size_t n, uint[] state);
state should have the length of repeat
pure nothrow @nogc @property @safe const(uint)[] front();
pure nothrow @nogc @safe void popFront();
const pure nothrow @nogc @property @safe size_t length();
const pure nothrow @nogc @property @safe bool empty();
pure nothrow @property @safe CartesianPower save();
void dispose(Allocator)(auto ref Allocator alloc, auto ref CartesianPower 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
perm CartesianPower object
pure nothrow @safe Combinations combinations(size_t n, size_t k = 1);

IndexedRoR!(Combinations, Range) combinations(Range)(Range r, uint k = 1)
if (isRandomAccessRange!Range);

Combinations makeCombinations(Allocator)(auto ref Allocator alloc, size_t n, size_t repeat);
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 range
size_t k number of combinations
Allocator alloc custom Allocator
Returns:
Forward range, which yields the k-combinations items
See Also:
struct Combinations;
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 std.algorithm: equal;
import std.range: iota;
assert(iota(3).combinations(2).equal!equal([[0, 1], [0, 2], [1, 2]]));
assert("AB"d.combinations(2).equal!equal(["AB"d]));
assert("ABC"d.combinations(2).equal!equal(["AB"d, "AC"d, "BC"d]));
Examples:
import std.algorithm: equal;
import std.range: 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(rc.indexedRoR(r).equal!equal(expected3r2));
alloc.dispose(rc);
pure nothrow @nogc @safe this(size_t n, uint[] state);
state should have the length of repeat
pure nothrow @nogc @property @safe const(uint)[] front();
pure nothrow @nogc @safe void popFront();
const pure nothrow @nogc @property @safe size_t length();
const pure nothrow @nogc @property @safe bool empty();
pure nothrow @property @safe Combinations save();
void dispose(Allocator)(auto ref Allocator alloc, auto ref Combinations combs);
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
perm Combinations object
pure nothrow @safe CombinationsRepeat combinationsRepeat(size_t n, size_t k = 1);

IndexedRoR!(CombinationsRepeat, Range) combinationsRepeat(Range)(Range r, size_t k = 1)
if (isRandomAccessRange!Range);

CombinationsRepeat makeCombinationsRepeat(Allocator)(auto ref Allocator alloc, size_t n, size_t repeat);
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 range
size_t k number of combinations
Allocator alloc custom Allocator
Returns:
Forward range, which yields the k-multicombinations items
struct CombinationsRepeat;
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 std.algorithm: equal;
import std.range: iota;

assert(iota(2).combinationsRepeat.equal!equal([[0], [1]]));
assert(iota(2).combinationsRepeat(2).equal!equal([[0, 0], [0, 1], [1, 1]]));
assert(iota(3).combinationsRepeat(2).equal!equal([[0, 0], [0, 1], [0, 2], [1, 1], [1, 2], [2, 2]]));
assert("AB"d.combinationsRepeat(2).equal!equal(["AA"d, "AB"d,  "BB"d]));
Examples:
import std.algorithm: equal;
import std.range: 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(rc.indexedRoR(r).equal!equal(expected3r1));
alloc.dispose(rc);
pure nothrow @nogc @safe this(size_t n, uint[] state);
state should have the length of repeat
pure nothrow @nogc @property @safe const(uint)[] front();
pure nothrow @nogc @safe void popFront();
const pure nothrow @nogc @property @safe size_t length();
const pure nothrow @nogc @property @safe bool empty();
pure nothrow @property @safe CombinationsRepeat save();
void dispose(Allocator)(auto ref Allocator alloc, auto ref CombinationsRepeat combs);
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
perm CombinationsRepeat object