How to List All Partitions of a Set
Suppose you have a number of distinct items, say five letters:
a b c d eA partition is a division of them without regard to order. One partition that divides the above into two parts is:
(a c) (b d e)
I call each part a “clump.” Some people call them “blocks” or “classes.” Whatever you call them, the order of the clumps, and of the items within each clump, is immaterial. Thus
(e d b) (a c)is the same partition as before.
There are exactly five partitions of three elements:
(a b c) ........ one clump
(a b) (c) ..... two clumps
(a c) (b) ..... two clumps
(a) (b c) ..... two clumps
(a) (b) (c) ... three clumps
The number of partitions of N items is known as the Bell number of N. The above shows that the Bell number of 3 is 5.
Someone, I don’t know who, invented a “partition representation” that specifies a partition numerically. “Partition representation” is what I call it. Some people call it a “restricted growth string” but they’re just showing off. First impose an (arbitrary) order on the N items by numbering them 1, 2, 3, ... N. Then a partition representation is a sequence of N numbers that describes which clump to put an item in. Before giving the complete definition consider an example. The representation for the partition of a b c d e we saw above
(a c) (b d e)is
1 2 1 2 2The idea is that there are two clumps, number them 1 and 2:
.. 1 ...... 2 ..and
(a c) (b d e)
item 1, a, goes in clump 1Thus 1 2 1 2 2 describes the partition. In general a partition representation Q(1) Q(2) ... Q(N) means element i goes in clump Q(i).
item 2, b, goes in clump 2
item 3, c, goes in clump 1
item 4, d, goes in clump 2
item 5, e, goes in clump 2
The representation is not unique, other sequences determine the same clumping. Partly this is because the representation depends on your arbitrary ordering of the items, but even if the ordering were fixed the partition still would not be unique. For example (keeping in mind that order doesn’t matter) 2 1 2 1 1 represents the same partition as 1 2 1 2 2 does. You could impose conditions, such as the first number is always 1, to improve the situation but there doesn’t seem to be any simple requirement that makes the representation unique.
A representation Q() for a partition of N items has the following two properties
1 is among the Q().And we can impose the condition
If k is among the Q() then so are all numbers preceding k.
Q(1) = 1.But if you started at the representation
1 1 1 1 . . . . . . . (a b c d ...)and went to
1 2 3 4 . . . . . . . (a) (b) (c) (d) ...passing through all sequences obeying the above three restrictions, there still would be repeats.
Now for an amazing algorithm described by Herbert Wilf and Albert Nijenhuis based on a formula due to James Stirling. It lists all the partition representations of N different elements without duplication. It is in code below, and I’ve added code that translates a given representation into its partition. Each line of the printout shows a partition and some information about it, in this order:
# of clumps, partition representation, size of each clump, the partitionIn the program these are:
np, Q(), P(), RepToPart()
The program is written for PBCC and can be modified for Visual Basic, FORTRAN and any other BASIC-like compiler.
Global N As Long 'number of items to be partitioned
Global np As Long 'number of clumps in the partition
Global P() As Long 'P(i) = number of items in the ith clump, i = 1 to np
Global Q() As Long 'Q(i) = clump to which i belongs, i = 1 to N
' Print the partition represented by Q() along with np, Q(), and P().
Local i, j As Long
Local a, b As String
ReDim part(N, N) As Long
ReDim npart(N) As Long
' Convert the partition representation Q() into a partition.
For i = 1 To N
For j = 1 To np
If Q(i) = j Then Exit For
part(j, npart(j)) = i
For j = 1 To np
a = "("
For i = 1 To npart(j)
a = a + Chr$(96 + (part(j, i)))
b = b + a + ")"
' Now b = the partition that Q() represents.
Print Format$(np);" ";
For j = 1 To N
Print " ";
For j = 1 To N
Print " "; b
' NextPartition uses an algorithm described
' by Albert Nijenhuis and Herbert Wilf in
' their book Combinatorial Algorithms.
' Given the partition represented by Q()
' [and P() and np, though these could be determined
' from Q()], find the next Q() [and its P() and np].
Local m, L As Long
Do Until np = N 'Both this condition and ...
m = N
L = Q(m)
If P(L) <> 1 Then Exit Do
Q(m) = 1
np = np + m - N
P(1) = P(1) + N - m
If L = np Then
P(np) = 0
Q(m) = L + 1
Incr P(L + 1)
Loop Until np <> N '... this condition are necessary.
P(np + 1) = 0 'Necessary only if you print P().
Local j, count As Long
N = 4 'change to suit
Dim P(N), Q(N)
For j = 1 To N 'start with Q() = 11111...1
Q(j) = 1
P(1) = N 'start with P() = 10000...0
np = 1 'one clump
If N = 1 Then GoTo Done
NextPartition 'changes np, P() and Q()
Loop Until np = N 'same condition as Q(N) = N
Print "Count: "; count 'the Bell number of N