|
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 + (k–j)
(the sum of rj
and the k–j 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 |
|