# 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

# Mathematica 16

Code

`Subsets` is native to Mathematica.

``````Column@Subsets@s
``````

The code (without column) can be verified on WolframAlpha. (I had to use brackets instead of `@`; they mean the same thing.

Usage

``````s={1,2,3}
Column@Subsets@s
``````

This method (55 chars) uses the approach suggested by @w0lf.

``````s #&/@Tuples[{0,1},Length@s]/.{0:>Sequence[]}//Column
``````

Breakdown

Generate the tuples, composed of `0` and `1`'s of length `Length[s]`

``````Tuples[{0, 1}, Length@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}}

Multiply the original list (vector) by each tuple:

``````s # & /@ Tuples[{0, 1}, Length@s]
``````

{{0, 0, 0}, {0, 0, 3}, {0, 2, 0}, {0, 2, 3}, {1, 0, 0}, {1, 0, 3}, {1, 2, 0}, {1, 2, 3}}

Delete the `0`'s. `%` is shorthand for "the preceding output".

%/. {0 :> Sequence[]}

{{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}

Display in column:

-
+1 This seems like cheating... – tjameson Nov 21 '12 at 22:56
@tjameson I had serious doubts about whether I should post it, but I thought some people might find it interesting to know it is built-in. – DavidC Nov 21 '12 at 23:05
I find it interesting :) – Dr. belisarius Nov 23 '12 at 11:48

## C, 118 115

Whilst can save approx 20 chars with simpler formatting, still not going to win in code golf terms either way.

``````x,i,f;
main(int a,char**s){
for(;x<1<<a;x+=2,puts("[]"+f))
for(i=f=0;++i<a;)x&1<<i?f=!!printf("%c%s","[,"[f],s[i]):0;
}
``````

Testing:

``````/a.out 1 2 3
[]
[1]
[2]
[1,2]
[3]
[1,3]
[2,3]
[1,2,3]
``````
-
Nice. Some tips: K&R style (`main(a,s)char**s;{...}`), `f|=x&1<<i&&printf` is shorter than `?:`. – ugoren Nov 22 '12 at 7:25
Just figured out what's behind `x+=2` (and where did `s[0]` go). Really nice trick. – ugoren Nov 22 '12 at 7:29

### GolfScript, 22 18 characters

``````~[[]]{{+}+1\$%+}@/`
``````

Another attempt in GolfScript with a completely different algorithm. Input format is the same as with w0lf's answer. (online test)

-
+1 Great solution! Mine is refactored for readability :-P – w0lf Nov 21 '12 at 20:23

## GolfScript (43 chars)

This may seem quite long, but it's the first solution to follow the spec: input is from command-line arguments, and output is newline-delimited.

``````"#{ARGV.join('
')}"n/[[]]\1/{`{1\$+.p}+%}%p;
``````

E.g.

``````\$ golfscript.rb powset.gs 1 2 3
["1"]
["2"]
["2" "1"]
["3"]
["3" "2"]
["3" "1"]
["3" "2" "1"]
[]
``````
-
Quotes aren't necessary, if that makes a difference. – tjameson Nov 21 '12 at 22:58
@tjameson, the quotes come from using the shortest possible way to print. The fact that those values are strings rather than integers comes from the inability of GolfScript to access command-line arguments directly: it has to rely on the interpreter doing an eval in Ruby and putting the result in a string. – Peter Taylor Nov 21 '12 at 23:04

# Python (74 70 chars)

``````def p(a,v):
if a:i,*a=a;p(a,v);p(a,v+[i])
else:print v
p(input(),[])
``````

for input as `1,2,3` or `[1,2,3]`, output is:

``````[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]
``````
-
`[a[0]]` = `a[:1]` – ugoren Nov 25 '12 at 17:51
with input `1,2,3` `a[:1]` not works. tuple+list not allowed. Exist better solution – AMK Nov 26 '12 at 13:21
+1 for `i,*a=a` – primo Nov 26 '12 at 14:43
Isn't `i,*a=a` Python 3? It doesn't work on my 2.7.1. – ugoren Nov 26 '12 at 15:02
Nor on 2.7.2. That might explain why I've never seen that trick before... most code golf servers run 2.7.x. – primo Nov 26 '12 at 15:24

## Python 70 67 bytes

``````def p(a,*v):
i=0;print v
for n in a:i+=1;p(a[i:],n,*v)
p(input())
``````

Input is taken in the same manner as for ugoren's solution. Sample I/O:

``````\$ echo [1,2,3] | powerset.py
()
(1,)
(2, 1)
(3, 2, 1)
(3, 1)
(2,)
(3, 2)
(3,)
``````
-
You can save some with `def p(a,*v)` and then `p(a[i:],n,*v)`. Output becomes somewhat uglier, but still OK. – ugoren Nov 26 '12 at 14:52
Very clever, thanks for the tip. – primo Nov 26 '12 at 15:07

## Golfscript 48

``````~:x,:§2\?,{[2base.,§\-[0]*\+x\]zip{~{}{;}if}%p}%
``````

This program uses the binary representations of numbers from 0 to length(input) to generate powerset items.

### Input

The input format is the Golfscript array format (example: `[1 2 3]`)

### Output

The output is a collection of arrays separated by newlines, representing the power set. Example:

``````[]
[3]
[2]
[2 3]
[1]
[1 3]
[1 2]
[1 2 3]
``````

### Online Test

The program can be tested online here.

-
Awesome, but could you delimit with newlines? – tjameson Nov 21 '12 at 9:43
@tjameson I managed to output delimited by newlines while keeping the same character count. Please see the update to my answer. – w0lf Nov 21 '12 at 9:51

## JavaScript, 98

Sadly, a good chunk is spent on output formatting.

``````for(n in a=eval(prompt(i=p=[[]])))
for(j=i+1;j;)
p[++i]=p[--j].concat(a[n]);
``````

### Input

Takes a JavaScript array. (e.g. [1,2,3])

### Output

``````[]
1
1,2
2
2,3
1,2,3
1,3
3
``````
-

## J, 19 chars

``````   (<@#~#:@i.@(2&^)@#)

(<@#~#:@i.@(2&^)@#) 1 2 3
┌┬─┬─┬───┬─┬───┬───┬─────┐
││3│2│2 3│1│1 3│1 2│1 2 3│
└┴─┴─┴───┴─┴───┴───┴─────┘
``````

The ascii boxing in the output is called `boxing` and provides heterogen collection (for different length of arrays here).

-

Mathematica 53

``````Column@Fold[#~Join~Table[x~Join~{#2},{x,#}]&,{{}},#]&
``````

-

Scala, 81

``````def p[A](x:Seq[A]){x.foldLeft(Seq(Seq[A]()))((a,b)=>a++a.map(b+:_)).map(println)}
``````
-

## Python 2, 64 bytes

Using comma-separated input:

``````P=[[]]
for i in input():P+=[s+[i]for s in P]
for s in P:print s
``````

## Pyth, 4 bytes (using builtin) or 14 bytes (without)

As noted by @Jakube in the comments, Pyth is too recent for this question. Still here's a solution using Pyth's builtin powerset operator:

``````jbyQ
``````

And here's one without it:

``````jbu+Gm+d]HGQ]Y
``````

You can try both solutions here and here. Here's an explanation of the second solution:

``````jb       # "\n".join(
u       #  reduce(
+G     #   lambda G,H: G+
m     #    map(
+d]H #     lambda d: d+[H],
G    #     G),
Q      #   input()
]Y     #   [[]]))
``````
-

## Python, 93 87 chars

Python makes formatting simple, because the required input/output matches its native format.
Only supports items which are Python literals (e.g. `1,2,'hello'`, not `1,2,hello`).

``````f=lambda x:x and f(x[1:])+[x[:1]+a for a in f(x[1:])]or[()]
for l in f(input()):print l
``````
-
`print f(input())` shorter – AMK Nov 24 '12 at 14:02
@AMK, the requirement is for each element to be printed in one line. But `list` can indeed be removed (if also replacinf `[[]]` with `[()]`. – ugoren Nov 24 '12 at 18:04
`print'\n'.join(f(input()))` saves two characters – beary605 Nov 24 '12 at 22:45
@beary605, doesn't work, `f()` contains tuples, not strings. – ugoren Nov 25 '12 at 5:24

```import Control.Monad
import System.Environment
main=getArgs>>=mapM print.filterM(\_->[False ..])
```

If importing `Control.Monad` isn't allowed, this becomes 100 characters:

```import System.Environment
main=getArgs>>=mapM print.p
p z=case z of{[]->[[]];x:y->p y++map(x:)(p y)}
```
-

## Ruby, 39

``````\$*.map{p *\$*.combination(\$.)
\$.+=1}
p\$*
``````
-

``````import System.Environment
main=getArgs>>=mapM print.p
p[]=[[]]
p(x:y)=(map(x:)\$p y)++p y
``````

Getting parameters is long :/

-

## APL (26)

Reads input from keyboard because there's no `argv` equivalent.

``````↑⍕¨(/∘T)¨↓⍉(M/2)⊤⍳2*M←⍴T←⎕
``````

Usage:

``````      ↑⍕¨(/∘T)¨↓⍉(M/2)⊤⍳2*M←⍴T←⎕
⎕:
1 2 3
3
2
2 3
1
1 3
1 2
1 2 3
``````

Explanation:

• `T←⎕`: read input, store in `T`
• `M←⍴T`: store length of `T` in `M`
• `(M/2)⊤⍳2*M`: generate the bit patterns for `1` upto `2^M` using `M` bits.
• `↓⍉`: split the matrix so that each bit pattern is separate
• `(/∘T)¨`: for each bit pattern, select those sub-items from `T`.
• `↑⍕¨`: for output, get the string representation of each element (so that it will fill using blanks and not zeroes), and format as a matrix (so that each element is on its own line).
-

# JavaScript (ES6) 76

Partially copied from this one: http://codegolf.stackexchange.com/a/51502/21348

Using a bitmap, so it's limited to no more than 32 elements.

Run the snippet in Firefox to test.

``````f=l=>{
for(i=0;i<1<<l.length;i++)
console.log(l.filter(v=>[i&m,m+=m][0],m=1))
}

// TEST

// Redefine console to have output inside the page
console = { log: (...p) => O.innerHTML += p.join(' ') + '\n' }

test=()=>{
var set = I.value.match(/[^ ,]+/g)
O.innerHTML='';
f(set);
}

test()``````
``#I,#O { border: 1px solid #aaa; width: 400px; padding:2px}``
``````Insert values, space or comma separated:<br>
<input id=I value='1 2 3'> <button onclick="test()">-></button>
<pre id=O></pre>``````

-

# C# 164

Man this is hard in C#!

``````void P<T>(T[]c){foreach(var d in c.Aggregate<T,IEnumerable<IEnumerable<T>>>(new[]{new T[0]},(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]{b})))))Console.WriteLine(d);}
``````
-

# K, 14 bytes

``````{x@&:'!(#x)#2}
``````

Generate all 0/1 vectors as long as the input, gather the indices of 1s and use those to select elements from the input vector. In practice:

``````  {x@&:'!(#x)#2} 1 2 3
(!0
,3
,2
2 3
,1
1 3
1 2
1 2 3)
``````

This is a bit liberal with the output requirements, but I think it's legal. The most questionable part is that the empty set will be represented in a type dependent form; `!0` is how K denotes an empty numeric vector:

``````  0#1 2 3      / integers
!0
0#`a `b `c   / symbols
0#`
0#"foobar"   / characters
""
``````

## Explanation

The `(#x)#2` builds a vector of `2` as long as the input:

``````  {(#x)#2}1 2 3
2 2 2
{(#x)#2}`k `d `b `"+"
2 2 2 2
``````

When monadic `!` is applied to a vector, it is "odometer":

``````  !2 2 2
(0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1)
``````

Then we use "where" (`&`) on each (`'`) vector to gather its indices. The colon is necessary to disambiguate between the monadic and dyadic form of `&`:

``````  &0 0 1 0 1 1
2 4 5

{&:'!(#x)#2} 1 2 3
(!0
,2
,1
1 2
,0
0 2
0 1
0 1 2)
``````

If we just wanted combination vectors, we'd be done, but we need to use these as indices into the original set. Fortunately, K's indexing operator `@` can accept a complex structure of indices and will produce a result with the same shape:

``````  {x@&:'!(#x)#2} `a `c `e
(0#`
,`e
,`c
`c `e
,`a
`a `e
`a `c
`a `c `e)
``````

Elegant, no?

-

# Mathematica, 51

More cheating:

``````Column@ReplaceList[Plus@@HoldForm/@#,x___+___->{x}]&
``````

Use with `@{1,2,3}`.

-
Your code should take the set as input, not just hardcode it. Also, since this is code golf, you should include the byte count of the code (and probably remove the unnecessary spaces). – Martin Ender Jun 12 '15 at 12:43
Since this contest is long over, the post was more for the idea, but I've edited it. – LogicBreaker Jun 12 '15 at 15:13

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

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

Python 74

``````def f(x):
for i in reduce(lambda s,e:s+[i+[e] for i in s],x,[[]]):print i
``````
-

## R, 63

``````y=lapply(seq(v),function(x)cat(paste(combn(v,x,s=F)),sep="\n"))
``````

Here, `v` represents a vector.

Usage:

``````v <- c(1, 2, 3)
y=lapply(seq(v),function(x)cat(paste(combn(v,x,s=F)),sep="\n"))
1
2
3
c(1, 2)
c(1, 3)
c(2, 3)
c(1, 2, 3)
``````
-

## Matlab (46)

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

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