<< Computer Algorithms Use  Ctrl +  or  –  to enlarge or reduce text size.

How to List All Partitions of a Set

Suppose you have a number of distinct items, say five letters:
a b c d e
A 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 2
The idea is that there are two clumps, number them 1 and 2:
.. 1 ...... 2 ..
(a c) (b d e)
and
item 1, a, goes in clump 1
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
Thus  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).

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().
If  k  is among the  Q()  then so are all numbers preceding  k.
And we can impose the condition
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 partition
In 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().
Sub PrintPartition
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
Next
Incr npart(j)
part(j, npart(j)) = i
Next

For j = 1 To np
a = "("
For i = 1 To npart(j)
a = a + Chr\$(96 + (part(j, i)))
Next
b = b + a + ")"
Next
' Now b = the partition that Q() represents.

Print Format\$(np);"  ";
For j = 1 To N
Print Format\$(Q(j));
Next
Print "  ";
For j = 1 To N
Print Format\$(P(j));
Next
Print "  "; b
End Sub
'-----------------------------------------------------

' 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].
Sub NextPartition
Local m, L As Long
Do Until np = N       'Both this condition and ...
m = N
Do
L = Q(m)
If P(L) <> 1 Then Exit Do
Q(m) = 1
Decr m
Loop
np = np + m - N
P(1) = P(1) + N - m
If L = np Then
Incr np
P(np) = 0
End If
Q(m) = L + 1
Decr P(L)
Incr P(L + 1)
Loop Until np <> N    '... this condition are necessary.
P(np + 1) = 0         'Necessary only if you print P().
End Sub
'-----------------------------------------------------

Function PBMain
Local j, count As Long

N = 4                    'change to suit

Dim P(N), Q(N)
'---------------------------

Q(j) = 1
Next
np = 1                   'one clump

PrintPartition
Incr count
If N = 1 Then GoTo Done

Do
NextPartition           'changes np, P() and Q()
PrintPartition
Incr count
Loop Until np = N        'same condition as Q(N) = N

Done:
Print
Print "Count: "; count   'the Bell number of N
WaitKey\$
End Function
```