Input description: An integer n.
Problem description: Generate (1) all or (2) a random or (3) the next integer or set partitions of length n. There are two different types of combinatorial objects denoted by the term ``partition'', namely integer partitions and set partitions. Although they are quite different beasts, it is a good idea to make both a part of your vocabulary:
into nonempty subsets.
For example, there are fifteen distinct set partitions of n=4:
{1234},
{123,4},
{124,3},
{12,34},
{12,3,4},
{134,2},
{13,24},
{13,2,4},
{14,23},
{1,234},
{1,23,4},
{14,2,3},
{1,24,3},
{1,2,34}, and
{1,2,3,4}.
Several of the problems in this catalog return set partitions as
results, such as vertex coloring and connected components.
Although the number of integer partitions grows exponentially with n, they do so at a refreshingly slow rate. There are only 627 partitions of n=20, and it is even possible to enumerate all partitions of n=100, since there there are only 190,569,292 of them.
The best way to generate all partitions is to construct them
in lexicographically decreasing order.
The first partition is 
itself.
The general rule is to subtract 1 from the smallest part that is >1
and then collect all
the 1's so as to match the new smallest part >1.
For example, the partition
after 
is 
,
since the five 1's left after 3-1=2 becomes the smallest part
are best packaged as 2,2,1.
When the partition is all 1's, we have completed one trip through all the
partitions.
This algorithm is not particularly complicated, but it is sufficiently intricate that you should consider using one of the implementations below. In either case, test it to make sure that you get exactly 627 distinct partitions for n=20.
Generating integer partitions uniformly at random is a trickier matter than generating random permutations or subsets. This is because selecting the first (i.e. largest) element of the partition has a dramatic effect on the number of possible partitions that can be generated. Observe that no matter how large n is, there is only one partition of n whose largest part is 1. The number of partitions of n with largest part at most k is given by the recurrence
with the two boundary conditions 
and 
.
This function can be used to select the largest part of your random partition
with the correct probabilities and, by proceeding recursively, to eventually
construct the entire random partition.
Implementations are cited below.
Figure: The Ferrers diagram of a random partition of n=1000
Random partitions tend to have large numbers of fairly small parts,
best visualized by a Ferrers diagram as in Figure 
.
Each row of the diagram corresponds to one part of the partition,
with the size of each part represented by that many dots.
Set partitions can be generated using techniques similar to integer
partitions.
Each set partition is encoded as a restricted growth function,
, where 
and
, for 
.
Each distinct digit identifies a subset, or block, of the partition,
while the growth condition ensures that the blocks are sorted into
a canonical order based on the smallest element in each block.
For example, the restricted growth function 0,1,1,2,0,3,1
defines the set partition
{{1,5}, {2,3,7}, {4}, {6} }.
Since there is a one-to-one equivalence between set partitions and restricted growth functions, we can use lexicographic order on the restricted growth functions to order the set partitions. Indeed, the fifteen partitions of {1,2,3,4} listed above are sequenced according to the lexicographic order of their restricted growth function (check it out).
To randomly generate set partitions, we use a similar counting strategy as with integer partitions. The Stirling numbers of the second kind S(n,k) count the number of partitions of 1,...,n with exactly k blocks. They are computed using the recurrence S(n,k) = S(n-1,k-1) + k*S(n-1,k) with the boundary conditions S(n,n)=1. The reader is referred to the references and implementations for more details and code.
Implementations:
The best source on generating combinatorial objects is
Nijenhuis and Wilf [NW78],
who provide efficient Fortran
implementations of algorithms to construct random and sequential
integer partitions, set partitions, compositions, and Young tableaux.
See Section for details on ftp-ing these programs.
An exciting WWW site developed by Frank Ruskey of the University of Victoria contains a wealth of material on generating combinatorial objects of different types, including permutations, subsets, partitions, and certain graphs. It is well worth checking this out at http://sue.csc.uvic.ca/~cos/.
Combinatorica [Ski90]
provides Mathematica implementations
of algorithms to construct random and sequential
integer partitions, compositions, strings, and Young tableaux,
as well as to count and manipulate these objects.
See Section .
Algorithm 403 [BL77] of the Collected Algorithms of the ACM is a Fortran code
for constructing integer partitions with k parts.
It is available from Netlib
(see Section ).
The Stanford GraphBase (see Section )
also contains generators for constructing all integer partitions.
Notes: The standard references on combinatorial generation [NW78, RND77, Rus97] all present algorithms for generating integer and/or set partitions. Andrews is the primary reference on integer partitions and related topics.
Interestingly, the set of all 52 set partitions for n=5 appears in the form of Murasaki diagrams in the oldest novel known, The Tale of Genji.
Two related combinatorial objects are Young tableaux and integer compositions, although they are less likely to emerge in applications. Generation algorithms for both are presented in [NW78, RND77, Rus97]
Young tableaux are two-dimensional configurations of integers {1,...,n} where the number of elements in each row is defined by an integer partition of n. Further, the elements of each row and column are sorted in increasing order, and the rows are left-justified. This notion of shape captures a wide variety of structures as special cases. They have many interesting properties, including the existance of a bijection between pairs of tableaux and permutations.
Compositions represent the set of possible assignments of a set of n indistinguishable balls to k distinguishable boxes. For example, we can place three balls into two boxes as {3,0}, {2,1}, {1,2}, or {0,3}. Compositions are most easily constructed sequentially in lexicographic order. To construct them randomly, pick a random (k-1)-subset of n+k-1 items using the algorithm of the previous section, and count the number of unselected items between the selected ones. For example, if k=5 and n=10, the (5-1)-subset {1,3,7,14} of 1,..., (n+k-1)=14 defines the composition {0,1,3,6,0}, since there are no items to the left of element 1 nor right of element 14.
Related Problems:
Generating permutations (see page ),
generating subsets (see page ).
