This post is about a simple way to operate on combinatorial sequences such as **permutations**, **combinations**, **partitions**, **correct bracket sequences**, etc., assuming *O*(*n* ^{2}) or in some cases *O*(*n* ^{3}) 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*(*n* ^{2}) 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.