Shortest power set implementation

Question

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.

Answer 1

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:

Answer 2

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]

Answer 3

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)

Answer 4

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"]
[]

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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]

Answer 10

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.

Answer 11

Jelly, 6 bytes

ŒPŒṘ€Y

Try it online!

ŒṘ€Y are string formatting.

Answer 12

Mathematica 53

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

Answer 13

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 2ⁿ-by-1 matrix, so each subset is on a separate line

Answer 14

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);}

Answer 15

Scala, 81

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

Answer 16

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

Answer 17

Haskell, 80 78 bytes

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

Try it online!

Answer 18

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>

Answer 19

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     #   [[]]))

Answer 20

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.

Answer 21

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

Answer 22

Ruby, 39

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

Answer 23

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

Answer 24

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

Answer 25

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)

Answer 26

Brachylog, 4 bytes

⊇ᵘẉᵐ

Try it online!

  ẉ     Write on its own line
 ᵘ ᵐ    every unique
⊇       subset of the input.

Answer 27

Mathematica, 51

More cheating:

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

Use with @{1,2,3}.

Answer 28

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?

Answer 29

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

Answer 30

Python 2, 74 bytes

def f(x):
    for i in reduce(lambda s,e:s+[i+[e] for i in s],x,[[]]):print i

Answer 31

Japt -R, 5 bytes

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

à pNÅ

Try it

Answer 32

Perl 6, 22 bytes

say words.combinations

The built in combinations method will give all N-combinations of a list, ie. the powerset. Arguments provided via STDIN

% echo 1 2 3 | ./powerset.p6
(() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

Answer 33

Japt -R, 5 bytes

à i[]

Try it online!

Answer 34

Common Lisp, 117 bytes

(labels((p(l &aux(x(car l)))(if x`(,@#1=(p(cdr l)),@(mapcar(lambda(m)(cons x m))#1#))'(()))))(mapcar'print(p(read))))

Input is a list of element, in output the sets are printed as lists (empty list is equal to NIL)

Try it online!

If the answer can be a function that returns the result, then:

Common Lisp, 90 bytes

(defun p(l &aux(x(car l)))(if x`(,@#1=(p(cdr l)),@(mapcar(lambda(m)(cons x m))#1#))'(())))

Try it online!

Answer 35

Coconut, 90 bytes

def p(l)=(fmap((+)$(l[:1]),p(l[1:])))+p(l[1:])if l else[[]]
fmap(print,p(input().split()))

I think I had something one byte shorter but I lost it after experimenting more.

Try it online!

Answer 36

PHP, 78 bytes

for(;$i<1<<$argc;$i+=2)for(print$c=_;$argc>$c+=1;)$i&1<<$c&&print"$argv[$c],";

prints a comma after each element and an underscore before each subset. Run with -nr or try it online.

Answer 37

05AB1E, 2 bytes

æ»

Try it online.

Output is space-delimited (i.e. 1 2 3). If you want it as actual lists (i.e. [1, 2, 3]), add €¸ before the »:

怸»

Try it online.

Explanation:

æ     # Take the powerset of the (implicit) input-list
   »  # Join the lists by newlines (and each inner list by spaces)
      # (and output the result implicitly)

 €¸   # Wrap each inner list into a list
      # (i.e. [[1],[1,2]] → [[[1]],[[1,2]]])

Answer 38

Zsh, 66 bytes

for ((;2**$#>i++;)){j=;for s
((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!

Answer 39

Python 2, 58 bytes

S=lambda A:A and[u+[A[0]]for u in S(A[1:])]+S(A[1:])or[[]]

Try it online!

Answer 40

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!

Answer 41

Matlab (46)

v=input(''),for i=1:numel(v),nchoosek(v,i),end

---

• the input must be of the form [% % % ..] where % is a number

Answer 42

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

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