indy256's blog

By indy256, 10 years ago, In English

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.

  • Vote: I like it
  • +83
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there any theory/source available for better understanding of this? I am not getting directly by reading this.