indy256's blog

By indy256, 7 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(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:

  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 2) 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

»
5 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.