The OpenD Programming Language

mir.combinatorics

This module contains various combinatorics algorithms.

Members

Functions

binomial
R binomial(T n, T k)

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.

cartesianPower
CartesianPower!T cartesianPower(size_t n, size_t repeat)
IndexedRoR!(CartesianPower!T, Range) cartesianPower(Range r, 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.

combinations
Combinations!T combinations(size_t n, size_t k)
IndexedRoR!(Combinations!T, Range) combinations(Range r, size_t k)

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

combinationsRepeat
CombinationsRepeat!T combinationsRepeat(size_t n, size_t k)
IndexedRoR!(CombinationsRepeat!T, Range) combinationsRepeat(Range r, size_t k)

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.

dispose
void dispose(Allocator alloc, 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.

dispose
void dispose(Allocator alloc, 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.

dispose
void dispose(Allocator alloc, 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.

dispose
void dispose(Allocator alloc, 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.

indexedRoR
IndexedRoR!(Collection, Range) indexedRoR(Collection collection, Range range)

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

makeCartesianPower
CartesianPower!T makeCartesianPower(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.

makeCombinations
Combinations!T makeCombinations(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.

makeCombinationsRepeat
CombinationsRepeat!T makeCombinationsRepeat(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.

makePermutations
Permutations!T makePermutations(Allocator alloc, size_t n)

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

permutations
Permutations!T permutations(size_t n)
IndexedRoR!(Permutations!T, Range) permutations(Range r)

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

Structs

CartesianPower
struct CartesianPower(T)

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

Combinations
struct Combinations(T)

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

CombinationsRepeat
struct CombinationsRepeat(T)

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.

IndexedRoR
struct IndexedRoR(Collection, Range)

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

Permutations
struct Permutations(T)

Lazy Forward range of permutations using Heap's algorithm.

Meta

Authors

Sebastian Wilzbach, Ilia Ki