# Shortest power set implementation

## Problem definition

Print out the powerset of a given set. For example:

[1, 2, 3] => [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]


Each element is to be printed on a separate line, so the above example would be printed as:

[]
[1]
[2]
...
[1, 2, 3]


## Example code (in D, python example here):

import std.stdio;

string[][] powerset(string[] set) {
if (set.length == 1) {
return [set, []];
}

string[][] ret;
foreach (item; powerset(set[1 .. $])) { ret ~= set[0]~item; ret ~= item; } return ret; } void main(string[] argv) { foreach (set; powerset(argv[1 ..$]))
writeln(set);
}


## Input

Elements will be passed as arguments. For example, the example provided above would be passed to a program called powerset as:

powerset 1 2 3


Arguments will be alphanumeric.

## Rules

1. No libraries besides io
2. Output does not have to be ordered
3. Powerset does not have to be stored, only printed
4. Elements in the set must be delimited (e.g. 1,2,3, [1,2,3] and ['1','2','3'] are acceptable, but 123 is not
• Trailing delimiters are fine (e.g. 1,2,3, == 1,2,3)
5. Best is determined based on number of bytes

The best solution will be decided no less than 10 days after the first submission.

• Closely related to codegolf.stackexchange.com/questions/6380 – Peter Taylor Nov 21 '12 at 22:55
• – edc65 Jun 12 '15 at 13:34
• If only this challenge was updated to allow the defaults, like returning and functions. Python would be 54 bytes: lambda L:reduce(lambda r,x:r+[s+[x]for s in r],L,[[]]). – mbomb007 Dec 21 '16 at 2:10
• I'm not agree in only print... Why not allow to have the data, the variable too.. Than why print in column and not in row? – user58988 Nov 15 '17 at 19:54

### Ruby Array method combination (from 1.9 ) [50 chars]

0.upto(ARGV.size){|a|ARGV.combination(a){|v| p v}}


## Matlab (46)

v=input(''),for i=1:numel(v),nchoosek(v,i),end


• the input must be of the form [% % % ..] where % is a number

# Perl 6, 22 bytes

say words.combinations


The built in combinations method will give all N-combinations of a list, ie. the powerset. Arguments provided via STDIN

% echo 1 2 3 | ./powerset.p6
(() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))


# Japt-R, 5 bytes

Sadly, Japt's built-in for getting the powerset of an array doesn't include the empty array or this would be 1 byte.

à pNÅ


Try it

# Japt-R, 5 bytes

à i[]


Try it online!

• Beat you to it! :p Also, note the (unnecessary) requirement of each element being on its own line. – Shaggy Jan 4 '19 at 16:17

((i&1<<j++))&&echo ${(P)j}' \c' echo}  Pretty standard nested for loop comparison, similar the C and js answers. Try it online! # Zsh, 71 bytes for s;a=($^@'
'$^a) for s ($a);b+=(${(j: :)${(uof)s}})
<<<${(F)${(u)b}}


Progressively builds up the cartesian product S^N, then eliminates repeated coordinates in a single element: (0 0 1 0 -> 0 1), then eliminates repeated elements: (0 1, 0 1 -> 0 1).

Here's an expanded version, with some examples:

for s in $@; do # 'for s in {a,b,c}' ensures we iterate 3 times cprod=(${^@}$'\n'${^cprod} )  # ex: {a,b,c}{aa,ab,ac,ba,bb,bc,ca,cb,cc}
done                               # (actually, $'a\na\na'$'a\na\nb' ...)
for xyz in $cprod; do # ex: xyz=$'a\nb\na'
unique_elems=${(uof)xyz} #$'a\nb\na' -(f)-> a b a -(o)-> a a b -(u)> a b
sets+=( ${(j: :)unique_elems} # a b -(j: :)> 'a b' done unique_sets=(${(u)sets})           # a 'a b' 'a b' b -(u)> a 'a b' b
<<< ${(F)unique_sets} # a 'a b' b -(F)>$'a\na b\nb'


Try it online!

# Python 2, 58 bytes

S=lambda A:A and[u+[A[0]]for u in S(A[1:])]+S(A[1:])or[[]]


Try it online!

# Pyth, 1 byte

y


Since Pyth has implicit Q (input variable) at the end of programs, this is basically just power set of the input. I don't think this violates any rules (although 'No libraries besides io' is a bit vague)

Try it online!

# PHP, 117

function f1($a1){$a2=[[]];
foreach($a1 as$a3){
foreach($a2 as$a4){
$a2[]=array_merge([$a3],$a4); } } return$a2;
}