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

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

(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)

is1 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(a c) (b d e)

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).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().

If k is among the Q() then so are all numbers preceding k.

And we can impose the conditionIf k is among the Q() then so are all numbers preceding k.

Q(1) = 1.

But if you started at the representation1 1 1 1 . . . . . . . (a b c d ...)

and went to1 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) '--------------------------- 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