Here are some basic combinatorial functions.
NumPartitions(n) computes number of partitions of n, i.e. how many distinct ways to write n as a sum of positive integers (error if n is negative)
SubsetIter(n) -- iterator for subsets of {0,1,...,n-1}
SubsetIter(n,k) -- iterator for cardinality k subsets of {0,1,...,n-1}
operator++() -- advance to next subset (advancing when ended does not trigger an error)
operator*() -- current subset as vector<long>
IsEnded(it) -- true iff it is one-past-the-last
Notes:
DegLex).
TupleIter(n,k) -- iterator for k-tuples of {0,1,...,n-1}
operator++() -- advance to next tuple (advancing when ended does not trigger an error)
operator*() -- current tuple as vector<long>
IsEnded(it) -- true iff it is one-past-the-last
Notes:
RandomSubsetIndices(n) -- returns a random subset of {0,1,2...,n-1}
RandomSubsetIndices(n,r) -- returns a size r random subset of {0,1,2...,n-1}
RandomTupleIndices(n,r) -- returns a random r-tuple from {0,1,2,...,n-1}
RandomPermutation(n) -- return vector<long> being a random permutation of {0,1,2,...,n-1}
signature(perm) -- return the signature of a permutation (of type vector<int> or vector<long>) of the values 0,1,2,..,n-1
Notes:
n indicates the range {0,1,2,...,n-1} so that the integers produced are valid indices into a C++ vector of size n.
vector<long>
The algorithm for RandomSubsetIndices(n,r) was taken from the
Wikipedia page on "Reservoir Sorting". Also RandomPermutation
was taken from Wikipedia (which page?)
Ugly fn names RandomSubsetIndices and RandomTupleIndices
For thread-safety the fns should also accept as input a random source!
2023
SubsetIter(n,k)
2022
RandomPermutation (fn has been there for a while)
2015