User:RE Boss/Power Set

Since Power Set is immutable, this copy was made.

---

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&.> #) {&.> <@]

Another possibility is applying one of the comb verbs and keeping the intermediate results, as the following explains.
Here the last combination calculated is 3 comb 5 , and the former results are kept.

++-+---+-------------------+
||0|0 1|+-----+-----+-----+|
||1|0 2||0 1 2|1 2 3|2 3 4||
||2|0 3||0 1 3|1 2 4|     ||
||3|0 4||0 1 4|1 3 4|     ||
||4|1 2||0 2 3|     |     ||
|| |1 3||0 2 4|     |     ||
|| |1 4||0 3 4|     |     ||
|| |2 3|+-----+-----+-----+|
|| |2 4|                   |
|| |3 4|                   |
++-+---+-------------------+

So, based on comb2 in Combinations, we get

ps4=: 3 : '(}:,;&.>@{:) (}:, [:({.,<@(i.@#,.&.>])@}.)[:,&.>/\.>@{:)^:y(y$<i.0 0)<@,<i.1 0'
ps4a=: ([:ps4 #) {&.> <	NB. for nouns which are not an integer atom.

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&.> #) {&.> <@]

ps4=: 3 : '(}:,;&.>@{:) (}:, [:({.,<@(i.@#,.&.>])@}.)[:,&.>/\.>@{:)^:y(y$<i.0 0)<@,<i.1 0'
ps4a=: ([:ps4 #) {&.> <	NB. for nouns which are not an integer atom.

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
)

Relative performance on i.20

place	rlprf	rlt	rls	verbs
5	38.09	9.25	4.12	ps0
3	19.48	8.03	2.43	ps1a
2	16.96	7.00	2.42	ps1b
4	21.56	8.89	2.42	ps2
1	6.96	2.73	2.55	ps3
0	1.00	1.00	1.00	ps4a

---

Contributed by Roger Hui. An earlier version of the text appeared in the J Forum on 2007-08-13.
 ps4 and relative perfomance was added by RE Boss.