This post is about a simple way to operate on combinatorial sequences such as permutations, combinations, partitions, correct bracket sequences, etc., assuming O(n2) or in some cases O(n3) time complexity per operation is acceptable (n — sequence length).
To refresh your knowledge here are all 3-combinations of 4 elements: 012, 013, 023, 123. And here are all correct bracket sequences of size 6: ((())), (()()), (())(), ()(()), ()()().
The common tasks solved on combinatorial sequences are the following:
- calculate total number of sequences
- generate all sequences
- given a sequence, find the next to it (like next_permutaion() in C++ STL)
- given a sequence, calculate its number
- given a sequence number, construct the sequence itself
It is sometimes rather involved to solve these tasks in O(n) or O(n * logn) time. If the time complexity is not a concern, you can brute force all sequences and implement checkValid() method to filter valid ones. This is the simplest, but simultaneously the slowest method.
As a tradeoff we can use a well-known idea and implement count(prefix) method. It calculates the number of sequences starting with prefix. This single method is all we need to run above 5 operations on many classes of combinatorial sequences. We will exploit object-oriented programming to create a tiny framework, consisting of a single class AbstractEnumeration.
Before looking at AbstractEnumeration class, let's see what amount of code we need to work for example with combinations:
public static class Combinations extends AbstractEnumeration {
final long[][] binomial;
public Combinations(int n, int k) {
super(n, k);
binomial = new long[n + 1][n + 1];
// calculate binomial coefficients in advance
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i; j++)
binomial[i][j] = (j == 0) ? 1 : binomial[i - 1][j - 1] + binomial[i - 1][j];
}
@Override
protected long count(int[] prefix) {
int size = prefix.length;
// if there is no combination with given prefix, 0 must be returned.
// by contract only the last element can make prefix invalid.
if (size >= 2 && prefix[size - 1] <= prefix[size - 2])
return 0;
// prefix is valid. return the number of combinations starting with prefix
int last = size > 0 ? prefix[size - 1] : -1;
return binomial[range - 1 - last][length - size];
}
}
Now we have the following methods at our disposal that solve above 5 tasks in O(n2) time:
- totalCount()
- enumerate()
- next()
- toNumber()
- fromNumber()
These methods are provided by AbstractEnumeration class. Source code is here
It is very easy to extend operations and implement prev(), first() and last() methods, etc.
Is there any theory/source available for better understanding of this? I am not getting directly by reading this.