### indy256's blog

By indy256, 7 years ago,

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:

1. calculate total number of sequences
2. generate all sequences
3. given a sequence, find the next to it (like next_permutaion() in C++ STL)
4. given a sequence, calculate its number
5. 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:

1. totalCount()
2. enumerate()
3. next()
4. toNumber()
5. 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.

• +83

 » 5 years ago, # |   +1 Is there any theory/source available for better understanding of this? I am not getting directly by reading this.