Code for playing with discrete combinatorial structures (i.e. combinations, permutations, n-tuples, etc.)
So far this library contains a few generators for the aforementioned structures. A generator is something that can be used to visit each instance of a combinatorial structure, one at a time. This allows you to explore the structure without exhausting memory.
The generators in this library implement the IteratorProtocol and Sequence protocols from the Swift standard library.
The algorithms for this library are from "The Art of Computer Programming, Volume 4a: Combinatorial Algorithms, part 1" by Donald E. Knuth.
An n-tuple can be thought of as a coordinate in an n-dimensional space. Since we're dealing with discrete structures, each dimension can be represented by the set non-negative integers, Z^*. Since computer resources are finite, each dimention typically has a finite domain. In this case we can view our n-tuple as a mixed radix number (m_1, m_2, ..., m_n), where each position i represents a digit with m_i possible values {0, 1, ..., (m_i-1)}. In this case each m_i is a radix.
Generates all n-tuples in the mixed-radix numbering system defined by an array of radixes in lexicographical order.
A permutation is a reordering of a sequence of elements, where each element is distinguishable.
Generates all permutations of a given array of integers, in lexicographic order.
"A combination of n things, taken t at a time, often called simply a t-combination of n things, is a way to select a subset of size t from a given set of size n." [1]
Combinations are often used to model cases where the order of the selected objects does not matter.
Generates all t-combinations of a given array of integers, in lexicographic order.
[1] "The Art of Computer Programming, Volume 4a: Combinatorial Algorithms, part 1", Donald E. Knuth, p. 355.