# 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 '12 at 22:55
• 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,[[]]). 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

# 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 '12 at 23:05
• I find it interesting :) Nov 23 '12 at 11:48
• Can you leave off the s and put the input at the end of the line? Jan 5 '19 at 14:21
• 15 bytes: Subsets/*Column makes an anonymous function that takes a list and returns the display in columns. Aug 28 '19 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 '12 at 7:25
• Just figured out what's behind x+=2 (and where did s[0] go). Really nice trick. Nov 22 '12 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 '19 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 '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. 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. Nov 21 '12 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 '17 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 '12 at 14:52
• Very clever, thanks for the tip. Nov 26 '12 at 15:07
• For the down-voter (over 7 years later), this is obviously Python 2. Mar 17 '20 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 '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. Nov 21 '12 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 '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 Nov 26 '12 at 14:43
• Isn't i,*a=a Python 3? It doesn't work on my 2.7.1. 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. Nov 26 '12 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}
((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!

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

# Japt-R, 5 1 byte

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

à


Try it (the empty line at the end is the empty set or you can run it with the -Q flag instead to visualise the sub-arrays)

## 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 [()]. Nov 24 '12 at 18:04
• print'\n'.join(f(input())) saves two characters Nov 24 '12 at 22:45
• @beary605, doesn't work, f() contains tuples, not strings. Nov 25 '12 at 5:24

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

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


import System.Environment

• one more char can be shaved off with map(x:)(p y)++p y and yet two more chars above that with [(x:),id]<*>p y. Apparently <*> is in the Prelude now. (filterM isn't). Sep 17 '16 at 22:33