The purpose of this page is to give an informal presentation of the algorithms I developed for my PhD thesis and subsequently turned into a research article. The basic gist of this work is that we can generate integer partitions much more effectively if we encode them as ascending compositions rather than the conventional descending compositions. As it turns out, it's much easier to generate ascending compositions. I'm not going to argue this point here, since it's something I've done at great length elsewhere; instead, lets just take a quick overview of the main points and look at the algorithms themselves.
Ascending Compositions
An integer partition is an expressions of a positive integer n as an unordered collection of positive integers. A composition, on the other hand, is an expresssion of n as an ordered collection of positive integers. For example, 1 + 1 + 2, 1 + 2 + 1 and 2 + 1 + 1 all represent the same partition of 4. Then, ascending compositions are the compositions of n where all the parts are in ascending (non decreasing) order. For example, the ascending compositions of 5 are:
1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 1 + 3 1 + 2 + 2 1 + 4 2 + 3 5
Generating ascending compositions is one way to get partitions: generating all ascending compositions is equivalent to generating all partitions. For historical reasons, partition generation algorithms have nearly all generated descending compositions (see Wikipedia), Mathworld or Ruskey's Combinatorial Object Server, for example). There are definite advantages, however, to working with ascending compositions instead.
Iterative Algorithm
Lets take a look at one algorithm to generate all ascending compositions. This algorithm is written as a Python generator, which is a very neat way of writing combinatorial generation algorithms.
def rule_asc(n):
a = [0 for i in range(n + 1)]
k = 1
a[1] = n
while k != 0:
x = a[k - 1] + 1
y = a[k] - 1
k -= 1
while x <= y:
a[k] = x
y -= x
k += 1
a[k] = x + y
yield a[:k + 1]
Although this algorithm is very simple, it is also very efficient. It is Constant Amortised Time, which means that the average computation per partition that is output is constant.
We can prove this fairly easily by looking at the two while loops and the variable k. Since the yield operator is called exactly once for every iteration of the outer while loop, we know that it must iterate exactly p(n) times (where p(n) is the number of partitions of n --- see Mathworld or Sloane's sequence A000041 for details and properties). Therefore, we know that there must be exactly p(n) decrement operations on k (since k -= 1 is only called in the outer loop). Then, since k is initially 1 and the algorithm terminates when k is 0, we know that there must be p(n) - 1 increment operations on k. Since the only increment operations occur in the inner while loop, we know that this loop gets executed exactly p(n) - 1 times, and so the total running time of the algorithm is proportional to p(n). In other words, the algorithm is constant amortised time.
Most Efficient Algorithm
If it's speed you're looking for, here is the most efficient known algorithm to generate all partitions of a positive integer.
def accel_asc(n):
a = [0 for i in range(n + 1)]
k = 1
y = n - 1
while k != 0:
x = a[k - 1] + 1
k -= 1
while 2 * x <= y:
a[k] = x
y -= x
k += 1
l = k + 1
while x <= y:
a[k] = x
a[l] = y
yield a[:k + 2]
x += 1
y -= 1
a[k] = x + y
y = x + y - 1
yield a[:k + 1]
This algorithm is a modification of the algorithm above. It gains its extra efficiency by using some structure of the set of ascending compositions to make many transitions more efficient. Consider, for example, the following of partitions of 10:
1 + 1 + 2 + 6 1 + 1 + 3 + 5 1 + 1 + 4 + 4
These transitions can be made very efficiently, since all we need to do is to add one to the second last part and subtract one from the last part. The algorithm above takes advantage of this, and it is the most efficient known algorithm to generate partitions (it has been shown to be more efficient than Zoghbi and Stojmenovic's excellent ZS1 algorithm.)