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