# 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 Nov 21, 2012 at 22:55
• Jun 12, 2015 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,[[]]). Dec 21, 2016 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, 2017 at 19:54

# 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:

• @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. Nov 21, 2012 at 23:05
• I find it interesting :) Nov 23, 2012 at 11:48
• Can you leave off the s and put the input at the end of the line? Jan 5, 2019 at 14:21
• 15 bytes: Subsets/*Column makes an anonymous function that takes a list and returns the display in columns. Aug 28, 2019 at 19:24

## 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 ?:. Nov 22, 2012 at 7:25
• Just figured out what's behind x+=2 (and where did s[0] go). Really nice trick. Nov 22, 2012 at 7:29
• Refusing to golf your answer because it's "still not going to win in code golf terms either way." makes the answer not a serious contender for the winning criteria of the challenge. Aug 25, 2019 at 1:22

~[[]]{{+}+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 Nov 21, 2012 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. Nov 21, 2012 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. Nov 21, 2012 at 23:04 ## awk (82) {for(;i<2^NF;i++){for(j=0;j<NF;j++)if(and(i,(2^j)))printf "%s ",$(j+1);print ""}}


assume saved in file powerset.awk, usage

$echo 1 2 3 | awk -f powerset.awk 1 2 1 2 3 1 3 2 3 1 2 3  ps if your awk doesn't have and() function, replace it with int(i/(2^j))%2 but adds two to the count. • (2^j) -> 2^j saves you 2 bytes; the .awk file also works without a trailing \n, so you could shave off another byte. Feb 7, 2017 at 3:16 ## 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]); alert('[]'+p.join('\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). ## 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,)


Try it online!

• You can save some with def p(a,*v) and then p(a[i:],n,*v). Output becomes somewhat uglier, but still OK. Nov 26, 2012 at 14:52
• Very clever, thanks for the tip. Nov 26, 2012 at 15:07
• For the down-voter (over 7 years later), this is obviously Python 2. Mar 17, 2020 at 9:49

## 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? Nov 21, 2012 at 9:43
• @tjameson I managed to output delimited by newlines while keeping the same character count. Please see the update to my answer. Nov 21, 2012 at 9:51

# 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] Nov 25, 2012 at 17:51
• with input 1,2,3 a[:1] not works. tuple+list not allowed. Exist better solution
– AMK
Nov 26, 2012 at 13:21
• Isn't i,*a=a Python 3? It doesn't work on my 2.7.1. Nov 26, 2012 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. Nov 26, 2012 at 15: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}
$b=[[]];foreach($a as $c)foreach($b as $d)$b[]=array_merge([$c],$d);return $b; }  # Go, 118 bytes package m func p(a ...int)[][]int{b:=[][]int{{}} for _,c:=range a{for _,d:=range b{b=append(b,append(d,c))}} return b}  # Zsh, 31 bytes Accidentally cut my previous byte-count in half answering another prompt... for i;a=({$i,}\ $^a) <<<${(F)a}


Try it online!

Delimiter is one or more spaces, we abuse trailing delimiters extensively here.