Essays/Power Set
A set s can be represented as an array whose items are its members. The power set of s is the set of all subsets of s . For example:
ps 0 1 2 ┌┬─┬─┬───┬─┬───┬───┬─────┐ ││2│1│1 2│0│0 2│0 1│0 1 2│ └┴─┴─┴───┴─┴───┴───┴─────┘ ps 3 4$'zeroone two ' ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ │two │one │one │zero│zero│zero│zero│ │ │ │ │two │ │two │one │one │ │ │ │ │ │ │ │ │two │ └────┴────┴────┴────┴────┴────┴────┴────┘ ps ;:'red green blue' ┌┬──────┬───────┬────────────┬─────┬──────────┬───────────┬────────────────┐ ││┌────┐│┌─────┐│┌─────┬────┐│┌───┐│┌───┬────┐│┌───┬─────┐│┌───┬─────┬────┐│ │││blue│││green│││green│blue│││red│││red│blue│││red│green│││red│green│blue││ ││└────┘│└─────┘│└─────┴────┘│└───┘│└───┴────┘│└───┴─────┘│└───┴─────┴────┘│ └┴──────┴───────┴────────────┴─────┴──────────┴───────────┴────────────────┘
The power set can be computed in several different ways.
Copy
The monad #: computes the binary representation; the power set obtains readily using the dyad # on the table of binary representations of i.2^#s and s itself. Thus:
s=: 0 1 2 ] b=: #:i.2^#s 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 b <@#"1 _ s ┌┬─┬─┬───┬─┬───┬───┬─────┐ ││2│1│1 2│0│0 2│0 1│0 1 2│ └┴─┴─┴───┴─┴───┴───┴─────┘ ps0=: #:@i.@(2&^)@# <@#"1 _ ]
Recursion
If t is the power set of }.s , then the power set of s obtains as t,({.s),&.>t . Hence:
ps1a=: 3 : 'if. 0=#y do. ,<0#y else. (<{.y) (],,&.>) ps1a }.y end.' ps1b=: ,@<@(0&#) ` (<@{. (],,&.>) $:@}.) @. (0<#)
Insert
2 (],,&.>) a: ┌┬─┐ ││2│ └┴─┘ 1 (],,&.>) 2 (],,&.>) a: ┌┬─┬─┬───┐ ││2│1│1 2│ └┴─┴─┴───┘ 0 (],,&.>) 1 (],,&.>) 2 (],,&.>) a: ┌┬─┬─┬───┬─┬───┬───┬─────┐ ││2│1│1 2│0│0 2│0 1│0 1 2│ └┴─┴─┴───┴─┴───┴───┴─────┘
The power set obtains by extending the empty set by _1{s , then extending the result of that by _2{s , then extending the result of that by _3{s , and so on. Thus:
ps2=: , @ ((],,&.>)/) @ (<"_1 , <@(0&#))
Combinations
The subsets can be grouped by size from 0 to #s and this grouped representation can be computed using combinations.
comb=: 4 : 0 NB. All size x combinations of i.y k=. i.>:d=.y-x z=. (d$<i.0 0),<i.1 0 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end. ; z ) 0 1 2 3 4 comb&.> 4 ┌┬─┬───┬─────┬───────┐ ││0│0 1│0 1 2│0 1 2 3│ ││1│0 2│0 1 3│ │ ││2│0 3│0 2 3│ │ ││3│1 2│1 2 3│ │ ││ │1 3│ │ │ ││ │2 3│ │ │ └┴─┴───┴─────┴───────┘ (0 1 2 3 4 comb&.> 4) {&.> <'abcd' ┌┬─┬──┬───┬────┐ ││a│ab│abc│abcd│ ││b│ac│abd│ │ ││c│ad│acd│ │ ││d│bc│bcd│ │ ││ │bd│ │ │ ││ │cd│ │ │ └┴─┴──┴───┴────┘ ps3=: (i.@>:@# comb&.> #) {&.> <@]
Collected Definitions
ps0 =: #:@i.@(2&^)@# <@#"1 _ ] ps1a=: 3 : 'if. 0=#y do. ,<0#y else. (<{.y) (],,&.>) ps1a }.y end.' ps1b=: ,@<@(0&#) ` (<@{. (],,&.>) $:@}.) @. (0<#) ps2 =: , @ ((],,&.>)/) @ (<"_1 , <@(0&#)) ps3 =: (i.@>:@# comb&.> #) {&.> <@] comb=: 4 : 0 NB. All size x combinations of i.y k=. i.>:d=.y-x z=. (d$<i.0 0),<i.1 0 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end. ; z )
Contributed by Roger Hui. An earlier version of the text appeared in the J Forum on 2007-08-13.