How to List All the Partitions of a Set

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)

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 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 Main
 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
 Next
 P(1) = N                 'start with P() = 10000...0
 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