Previous Entry Next Entry→

September 26, 2005

After hunting on the internet and finding various pages with cryptic info on partitions, I find in my very own library a tome entitled Combinatorical Algorithms, by Albert Nijenhuis and Herbert S. Wilf, Academic Press, 1975.

For a positive integer n we define

n = r1 + r2 + r3 + . . . + rk   (r1 r2 r3 . . . rk )

to be a partition of n.  where each of the k parts are understood to be positive integers.  The arrangements I've been writing so far have, amazingly, a name: antilexicographic (reversed dictionary) order.  More precisely, a partition

n = r1 + r2 + r3 + . . . + rk

appears above

n = s1 + s2 + s3 + . . . + sk

if, reading from left to right, the first instance of ri ≠ si  has  ri > si

The plan is to generate the partitions in antilexicographic order and the question, then, is how to compute, for a given partition

n = r1 + r2 + r3 + . . . + rk

the immediate successor

n = ř1 + ř2 + ř3 + . . . + řq

Let's consider two separate cases: either the last element of the given partition is  rk = 1 or not. If it's not, then the next partition is obtained simply by n = r1 + r2 + r3 + . . . + (rk–1) + 1 and q = k + 1.

Now suppose that there is a string one or more 1's at the tail end of the partition and that the last part greater than 1 is rj.  Initially it may seem that the case where rj = 2 and the case where it is bigger than 2 may need to be considered separately.  If  rj = 2 then we simply replace it by a pair of 1's; if rj > 2 then we need to regroup all the 1's. But these may turn out in the end to amount to the same result...maybe...depending--see tomorrow's entry.

First note that none of the first j–1 parts will change so that

ři =  ri for i < j

and there are n' = rj + (kj) (the sum of rj and the kj 1's) to regroup at the j position in such a way that they form the partition of rj–1 with the fewest parts.  Such a partition is formed by floor(n'/m) repetitions of  m = rj–1, followed by the remainder,  n'm*floor(n'/m), unless the remainder is zero.

A quick example:  what partition immediately follows 4-1-1-1-1-1-1-1-1-1 ?
Here r1 = 4,  j = 1, k = 10 and so the 'regroup' value is

n' = 4 + (10–1) = 13.

Now,  m = 4-1 = 3 and  floor(n'/m) = floor(13/3) = 4 and

n' m*floor(n'/m) = 13 - 3*4 = 1.

Thus the next partition in antilexicographic order is 3-3-3-3-1.

The pseudocode for handling the case where  rj > 1 and  rj+1 = rj+2 =  . . . = rk = 1 can be written as follows:

 ři =  ri for i = 1, 2, ... ,j–1 řj =  řj+1  =  . . . =   řj+u-1 = m řj+u = s  where m = rj–1, u = floor((rj + (k–j))/m), s = rj + (k–j) – m*u

http://www.math.mtu.edu/~kreher/cages.html