Back to July Calendar

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 + . . . + (rk1) + 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 j1 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 rj1 with the fewest parts.  Such a partition is formed by floor(n'/m) repetitions of  m = rj1, 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 + (101) = 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, ... ,j1
řj
=  řj+1  =  . . . =
  řj+u-1 = m
ř
j+u = s

 where m = rj1, u = floor((rj + (kj))/m), s = rj + (kj) m*u

 

http://www.btinternet.com/~se16/js/partitions.htm

http://www.ece.utexas.edu/~garg/

http://www.delphiforfun.org/Programs/Math_Topics/Integer_partitions.htm

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