# Essays/Set Partitions

A *set partition* is a collection of disjoint subsets
whose union is the whole set.

For a given set magnitude `N`, the verb `setpart` finds all set partitions
in the form of subset keys (the left argument of dyadic `/.`). For example:

p ; 'abcd' ;:^:_1@(</.)"1~ p=. setpart 4 +-------+-------+ |0 0 0 0|abcd | |0 0 0 1|abc d | |0 0 1 0|abd c | |0 0 1 1|ab cd | |0 0 1 2|ab c d | |0 1 0 0|acd b | |0 1 0 1|ac bd | |0 1 0 2|ac b d | |0 1 1 0|ad bc | |0 1 1 1|a bcd | |0 1 1 2|a bc d | |0 1 2 0|ad b c | |0 1 2 1|a bd c | |0 1 2 2|a b cd | |0 1 2 3|a b c d| +-------+-------+

### Iterative Solution

nextpart=: (#~ ,"1 0 ;@:(i.&.>)@]) >:@#@~."1 setpart=: nextpart^:(]`(''"_))

How it works:: We note that the next generation is obtained from the previous by

- taking each row
- finding its
`nub+1`indices`i.>:#~`. - appending each of the indices to a copy of the row

nextpart 1 2$0 0 0 0 0 0 0 1 nextpart 1 2$0 1 0 1 0 0 1 1 0 1 2

### Factorial Base

Mike Day posted a
solution
based on factorial base representation, `1 2 3 ...` . Compare
with uniform base, `3 3 3`:

|: (>:@i. #: i.@! ) 3 NB. increasing base 0 0 0 0 0 0 0 0 0 1 1 1 0 1 2 0 1 2 |: (#~ #: i.@^~) 3 NB. full base 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2

Complete set of elements for these bases is respectively
`0..N!-1` and `0..N^N-1`. The latter includes the former.

The complete factorial base representation contains
the all key subsets list. So the second step is to
filter out the extraneous elements. Mike noted that
those elements, when selfnubbed `(i.~ ~.)` blend with
proper key subsets and can be filtered out with nub
over the whole list.

(,:&|: (i.~ ~.)"1) (>:@i. #: i.@!) 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 2 2 2 2 0 0 0 0 1 1 1 1 2 2 2 2 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 2 2 2 2 0 1 1 1 0 1 2 2 0 2 1 2 0 1 2 2 0 1 2 2 0 1 2 3 ~: (i.~ ~.)"1 (>:@i. #: i.@!) 4 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1

It's a correct solution, but it will require
`O(!N)` space, whereas the order of space for
the resulting list is roughly `O(2^(N^1.28))`.

`plot ^.(( 2&^)@(^&1.28)@<: ,: #@allsskeys"0) 1+i.8`

So question is how to avoid generating full !N list of representations. One possibility is with the cost of speed filter out extraneous items early.

factrep=: >:@i. #: i.@! selfnub=: i.~ ~. setpart1=: [: ~. [: selfnub"1 factrep

We note that good items are fixed under selfnubbing operation:

setpart2=: (#~ (-: selfnub)"1)@factrep (setpart1 -: setpart2) 5 1

So we will filter before generating the full array:

setpart3=: >:@i. ([ #: (-: selfnub)@#: # ]) i.@! ts'setpart1 8' 0.126269 4.71981e6 ts'setpart3 8' 0.135883 558144

It is negligibly longer, but has space for one step more.
That's about it for space optimization, however the
iterative `setpart` solution is much more optimal in time.

ts'setpart 8' 0.00350743 530496

### Set Partition Index

Because of the full subset keys is space thirsty, it is feasible to have, in addition, operations of subset key index and getting i-th subset key given order n and index i. Compare

### Partitions of Sets with Non-unique Elements

Further, the target set, to which keys are applied, may contain non-unique elements, so different keys may give the same result

(0 0 1;0 1 0) ]/.&.> <'abb' +--+--+ |ab|ab| |b |b | +--+--+

which creates a problem of finding keys with unique results for a set with non-unique elements.

### Application

Combinations of all factorings from a list of prime factors.

~. (<@/:~@(*//.)"1~ setpart@#) q:24 +--+---+----+---+-----+-----+-------+ |24|3 8|2 12|4 6|2 3 4|2 2 6|2 2 2 3| +--+---+----+---+-----+-----+-------+

### Generate Set Partitions - K Subsets

Generate all set partitions with k subsets from an original set with n unique items. J definition created by Erling Hellenäs from a Frank Ruskey algorithm.

SetPartitionsGenerateF =: 4 : 0 NB. Generate all set partitions with k subsets from NB. an original set with n unique items. NB. x - number of subsets NB. y - number of items in the set to partition NB. Result - table of integers NB. -each row is a generated set partition NB. -columns contain the subset number of the items NB. with the corresponding position in the set to NB. partition. NB. Algorithm from Frank Ruskey: Combinatorial Generation NB. Working Version (1j-CSC 425/520). (,: i.y) SPGF (x-1);y-1 ) SPGF =: 4 : 0 'k n' =. y r=. (0,_1{.$x)$0 if. k=n do. r=.x else. s=.n {."1 x e=.(n+1)}."1 x a=.,/s ( [,"1 1 (i.k+1),"0 1 ])"1 e r=.r, a SPGF k;n-1 if. k > 0 do. a=.s,.k,.e r=.r, a SPGF (k-1);n-1 end. end. r )

### See also

- MathWorld:SetPartition, Mathworld
- OEIS:A000110, Sloane. Bell or exponential numbers: ways of placing n labeled balls into n indistinguishable boxes.
- Factorings
- Divisors
- Frank Ruskey: Combinatorial Generation, Working Version (1j-CSC 425/520)
- Kenneth P. Bogart: Combinatorics Through Guided Discovery

Contributed by Oleg Kobchenko and Erling Hellenäs.