27
\$\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\$
4
  • \$\begingroup\$ Closely related to codegolf.stackexchange.com/questions/6380 \$\endgroup\$ Nov 21, 2012 at 22:55
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/51468/21348 \$\endgroup\$
    – edc65
    Jun 12, 2015 at 13:34
  • 3
    \$\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, 2016 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\$
    – user58988
    Nov 15, 2017 at 19:54

45 Answers 45

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\$
4
  • \$\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, 2012 at 23:05
  • \$\begingroup\$ I find it interesting :) \$\endgroup\$ Nov 23, 2012 at 11:48
  • \$\begingroup\$ Can you leave off the s and put the input at the end of the line? \$\endgroup\$ Jan 5, 2019 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, 2019 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\$
3
  • \$\begingroup\$ Nice. Some tips: K&R style (main(a,s)char**s;{...}), f|=x&1<<i&&printf is shorter than ?:. \$\endgroup\$
    – ugoren
    Nov 22, 2012 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, 2012 at 7:29
  • 1
    \$\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\$ Aug 25, 2019 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\$
1
  • \$\begingroup\$ +1 Great solution! Mine is refactored for readability :-P \$\endgroup\$ Nov 21, 2012 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\$
2
  • \$\begingroup\$ Quotes aren't necessary, if that makes a difference. \$\endgroup\$
    – beatgammit
    Nov 21, 2012 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\$ Nov 21, 2012 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\$
1
  • \$\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, 2017 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\$

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\$
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,)

Try it online!

\$\endgroup\$
3
  • 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, 2012 at 14:52
  • \$\begingroup\$ Very clever, thanks for the tip. \$\endgroup\$
    – primo
    Nov 26, 2012 at 15:07
  • \$\begingroup\$ For the down-voter (over 7 years later), this is obviously Python 2. \$\endgroup\$
    – primo
    Mar 17, 2020 at 9:49
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\$
2
  • \$\begingroup\$ Awesome, but could you delimit with newlines? \$\endgroup\$
    – beatgammit
    Nov 21, 2012 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\$ Nov 21, 2012 at 9:51
2
\$\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\$
5
  • \$\begingroup\$ [a[0]] = a[:1] \$\endgroup\$
    – ugoren
    Nov 25, 2012 at 17:51
  • \$\begingroup\$ with input 1,2,3 a[:1] not works. tuple+list not allowed. Exist better solution \$\endgroup\$
    – AMK
    Nov 26, 2012 at 13:21
  • \$\begingroup\$ +1 for i,*a=a \$\endgroup\$
    – primo
    Nov 26, 2012 at 14:43
  • \$\begingroup\$ Isn't i,*a=a Python 3? It doesn't work on my 2.7.1. \$\endgroup\$
    – ugoren
    Nov 26, 2012 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, 2012 at 15:24
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\$

Ruby, 39

$*.map{p *$*.combination($.)
$.+=1}
p$*
\$\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\$

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
  • 2
    \$\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, 2018 at 18:10
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\$
0
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\$
1
  • \$\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, 2018 at 12:59
2
\$\begingroup\$

Jelly, 6 bytes

ŒPŒṘ€Y

Try it online!

ŒṘ€Y are string formatting.

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

Python 2, 63 bytes

def f(s,p=[[]]):
 for e in s:
  for u in p:p=p+[u+[e]]
 print p

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Note that the spec (unnecessarily) requires each element to be output on its own line. \$\endgroup\$
    – Shaggy
    Aug 4, 2021 at 19:59
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\$
3
  • \$\begingroup\$ Why the alert? \$\endgroup\$
    – Shaggy
    Feb 2, 2018 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, 2018 at 14:21
  • \$\begingroup\$ Ah, fair enough; I interpreted "print" as "output". \$\endgroup\$
    – Shaggy
    Feb 2, 2018 at 14:22
1
\$\begingroup\$

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!

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

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)

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

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.

\$\endgroup\$
0
\$\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\$
4
  • \$\begingroup\$ print f(input()) shorter \$\endgroup\$
    – AMK
    Nov 24, 2012 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, 2012 at 18:04
  • \$\begingroup\$ print'\n'.join(f(input())) saves two characters \$\endgroup\$
    – beary605
    Nov 24, 2012 at 22:45
  • \$\begingroup\$ @beary605, doesn't work, f() contains tuples, not strings. \$\endgroup\$
    – ugoren
    Nov 25, 2012 at 5:24
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.