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 right 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

   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 -: setpart 2) 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 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.