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.