Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
Closely related to codegolf.stackexchange.com/questions/6380 –  Peter Taylor Nov 21 '12 at 22:55
add comment

20 Answers

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

output


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:

Mathematica graphics

share|improve this answer
    
+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. –  David Carraher Nov 21 '12 at 23:05
    
I find it interesting :) –  belisarius Nov 23 '12 at 11:48
add comment

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]
share|improve this answer
    
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
add comment

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)

share|improve this answer
    
+1 Great solution! Mine is refactored for readability :-P –  w0lf Nov 21 '12 at 20:23
add comment

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"]
[]
share|improve this answer
    
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
add comment

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]
share|improve this answer
    
[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
add comment

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,)
share|improve this answer
1  
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
add comment

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.

share|improve this answer
    
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
add comment

Mathematica 53

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

enter image description here

share|improve this answer
add comment

Scala, 81

def p[A](x:Seq[A]){x.foldLeft(Seq(Seq[A]()))((a,b)=>a++a.map(b+:_)).map(println)}
share|improve this answer
add comment

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
share|improve this answer
add comment

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).
Reads standard input, not parameters.

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
share|improve this answer
    
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
add comment

Haskell (96)

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)}
share|improve this answer
add comment

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).

share|improve this answer
add comment

Ruby, 39

$*.map{p *$*.combination($.)
$.+=1}
p$*
share|improve this answer
add comment

Haskell 89 chars

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

Getting parameters is long :/

share|improve this answer
add comment

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);}
share|improve this answer
add comment

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

0.upto(ARGV.size){|a|ARGV.combination(a){|v| p v}}
share|improve this answer
add comment

Python 74

def f(x):
    for i in reduce(lambda s,e:s+[i+[e] for i in s],x,[[]]):print i
share|improve this answer
add comment

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).
share|improve this answer
add comment

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)
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.