22
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Closely related to codegolf.stackexchange.com/questions/6380 \$\endgroup\$ – Peter Taylor Nov 21 '12 at 22:55
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/51468/21348 \$\endgroup\$ – edc65 Jun 12 '15 at 13:34
  • 2
    \$\begingroup\$ 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,[[]]). \$\endgroup\$ – mbomb007 Dec 21 '16 at 2:10
  • \$\begingroup\$ 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? \$\endgroup\$ – RosLuP Nov 15 '17 at 19:54

42 Answers 42

15
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – DavidC Nov 21 '12 at 23:05
  • \$\begingroup\$ I find it interesting :) \$\endgroup\$ – Dr. belisarius Nov 23 '12 at 11:48
  • \$\begingroup\$ Can you leave off the s and put the input at the end of the line? \$\endgroup\$ – Solomon Ucko Jan 5 at 14:21
  • \$\begingroup\$ 15 bytes: Subsets/*Column makes an anonymous function that takes a list and returns the display in columns. \$\endgroup\$ – Roman Aug 28 at 19:24
9
\$\begingroup\$

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

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)

\$\endgroup\$
  • \$\begingroup\$ +1 Great solution! Mine is refactored for readability :-P \$\endgroup\$ – Cristian Lupascu Nov 21 '12 at 20:23
5
\$\begingroup\$

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"]
[]
\$\endgroup\$
  • \$\begingroup\$ Quotes aren't necessary, if that makes a difference. \$\endgroup\$ – beatgammit Nov 21 '12 at 22:58
  • \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Nov 21 '12 at 23:04
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ (2^j) -> 2^j saves you 2 bytes; the .awk file also works without a trailing \n, so you could shave off another byte. \$\endgroup\$ – mklement0 Feb 7 '17 at 3:16
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

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,)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save some with def p(a,*v) and then p(a[i:],n,*v). Output becomes somewhat uglier, but still OK. \$\endgroup\$ – ugoren Nov 26 '12 at 14:52
  • \$\begingroup\$ Very clever, thanks for the tip. \$\endgroup\$ – primo Nov 26 '12 at 15:07
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Awesome, but could you delimit with newlines? \$\endgroup\$ – beatgammit Nov 21 '12 at 9:43
  • \$\begingroup\$ @tjameson I managed to output delimited by newlines while keeping the same character count. Please see the update to my answer. \$\endgroup\$ – Cristian Lupascu Nov 21 '12 at 9:51
2
\$\begingroup\$

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)}
\$\endgroup\$
2
\$\begingroup\$

Mathematica 53

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

enter image description here

\$\endgroup\$
2
\$\begingroup\$

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).
\$\endgroup\$
2
\$\begingroup\$

Scala, 81

def p[A](x:Seq[A]){x.foldLeft(Seq(Seq[A]()))((a,b)=>a++a.map(b+:_)).map(println)}
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6) 76

Partially copied from this one: https://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>

\$\endgroup\$
2
\$\begingroup\$

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);}
\$\endgroup\$
2
\$\begingroup\$

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     #   [[]]))
\$\endgroup\$
2
\$\begingroup\$

brainfuck, 94 bytes

+[[<+>>+<-]++[>-<------]>-[>]<<[>>+>]>,]++++++++++[[[<]<]+[-[>[.>]]<[<]>+[>]>]<<
.[<<[<]>-]++>]

Formatted:

+
[
  [<+> >+<-]
  ++[>-<------]>-[>]
  <<[>>+>]
  >,
]
++++++++++
[
  [[<]<]
  +
  print
  [
    -[>[.>]]
    <[<]
    >+[>]
    >
  ]
  <<.
  increment
  [
    <<[<]
    >-
  ]
  ++>
]

Expects input of the form 9,10,11 without a trailing newline, and outputs subsets in the same format, sometimes with a trailing comma. The first line printed will always be empty, signifying the empty set.

Try it online.

The basic idea is to place a bit next to each element, then repeatedly increment the binary number while printing the corresponding subset before each increment. (A bit indicates whether an element is in the subset.) A sentinel bit to the left of the array is used to terminate the program. This version actually creates an exponential number of sentinels to save some bytes; a more efficient 99-byte solution that only uses one sentinel can be found in the revision history.

Each bit is encoded as one plus its value; i.e., it can be either 1 or 2. The tape is laid out with the bit before each element and a single zero cell between adjacent elements. The comma is included on the tape for non-final elements, so we can conveniently just print elements without doing any extra work to handle delimiters.

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Classic), 13 bytes

⍪,⊃∘.,/⎕,¨⊂⊂⍬

Try it online!

Output:

 1 2 3 
 1 2   
 1 3   
 1     
 2 3   
 2     
 3     

There's a blank line at the end to represent the empty set.

Explanation:

evaluated input

⎕,¨⊂⊂⍬ append an empty numeric list after each element

∘., Cartesian product

/ reduction (foldr)

disclose (necessary after reduction in APL)

At this point the result is an n-dimensional 2-by-...-by-2 array, where n is the length of the input.

, flatten into a vector

turn the vector into an upright 2n-by-1 matrix, so each subset is on a separate line

\$\endgroup\$
2
\$\begingroup\$

Haskell, 80 78 bytes

import System.Environment
main=getArgs>>=mapM(print.concat).mapM(\a->[[a],[]])

Try it online!

\$\endgroup\$
  • \$\begingroup\$ The I/O requirements are horrible, however people are interpreting them quite loosely. If you change to taking input via stdin you could save 15 bytes, see this. \$\endgroup\$ – ბიმო Apr 23 '18 at 12:59
2
\$\begingroup\$

Jelly, 6 bytes

ŒPŒṘ€Y

Try it online!

ŒṘ€Y are string formatting.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ print f(input()) shorter \$\endgroup\$ – AMK Nov 24 '12 at 14:02
  • \$\begingroup\$ @AMK, the requirement is for each element to be printed in one line. But list can indeed be removed (if also replacinf [[]] with [()]. \$\endgroup\$ – ugoren Nov 24 '12 at 18:04
  • \$\begingroup\$ print'\n'.join(f(input())) saves two characters \$\endgroup\$ – beary605 Nov 24 '12 at 22:45
  • \$\begingroup\$ @beary605, doesn't work, f() contains tuples, not strings. \$\endgroup\$ – ugoren Nov 25 '12 at 5:24
1
\$\begingroup\$

Ruby, 39

$*.map{p *$*.combination($.)
$.+=1}
p$*
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Will Ness Sep 17 '16 at 22:33
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ This is no longer valid, as "odometer" in oK now generates a flipped matrix. It can be corrected at the cost of a single byte: {x@&:'+!(#x)#2}. Unrelated: a shorter equivalent of (#x)#2 is 2|~x. \$\endgroup\$ – ngn Feb 2 '18 at 18:10
1
\$\begingroup\$

Mathematica, 51

More cheating:

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

Use with @{1,2,3}.

\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Martin Ender Jun 12 '15 at 12:43
  • \$\begingroup\$ Since this contest is long over, the post was more for the idea, but I've edited it. \$\endgroup\$ – LogicBreaker Jun 12 '15 at 15:13
1
\$\begingroup\$

JavaScript (ES6), 68 bytes

a=>alert(a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).join`
`)

Demo

let f =

a=>alert(a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).join`
`)

f([1,2,3])

\$\endgroup\$
  • \$\begingroup\$ Why the alert? \$\endgroup\$ – Shaggy Feb 2 '18 at 14:16
  • \$\begingroup\$ @Shaggy The challenge explicitly asks to print each element on a separate line -- which would probably frowned upon with our current standards. Most answers seem to stick to this rule. \$\endgroup\$ – Arnauld Feb 2 '18 at 14:21
  • \$\begingroup\$ Ah, fair enough; I interpreted "print" as "output". \$\endgroup\$ – Shaggy Feb 2 '18 at 14:22
1
\$\begingroup\$

Brachylog, 4 bytes

⊇ᵘẉᵐ

Try it online!

  ẉ     Write on its own line
 ᵘ ᵐ    every unique
⊇       subset of the input.
\$\endgroup\$
0
\$\begingroup\$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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