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