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
)

Essays/Set Partitions

Contents

Iterative Solution

Factorial Base

Set Partition Index

Partitions of Sets with Non-unique Elements

Application

Generate Set Partitions - K Subsets

See also

Navigation menu

Search