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

Thunno 2, 3 bytes

ʠ¶j

Try it online!

Explanation

ʠ¶j  # Implicit input
ʠ    # Take the powerset
 ¶j  # Join on newlines
     # Implicit output

Answer 2

Nekomata, 1 byte

S

Attempt This Online!

S finds a subset of a list.

By default, Nekomata prints all possible results separated by newlines.

Answer 3

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 4

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

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

Answer 5

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 6

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 7

Mathematica, 51

More cheating:

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

Use with @{1,2,3}.

Answer 8

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 9

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 10

Japt -R, 5 bytes

à i[]

Try it online!

Answer 11

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 12

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 13

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 14

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 15

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 16

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 17

PostScript, 80 bytes

00000000: 921a 2f6c 923e 9233 3088 0132 206c 2065  ../l.>.30..2 l e
00000010: 7870 2031 92a9 7b2f 6e92 3e92 335b 3088  xp 1..{/n.>.3[0.
00000020: 016c 2031 92a9 7b6e 2032 926a 3192 3d7b  .l 1..{n 2.j1.={
00000030: 921b 9201 9258 7d7b 9275 7d92 552f 6e20  .....X}{.u}.U/n 
00000040: 6e88 ff92 0f92 337d 9248 5d3d 3d7d 9248  n.....3}.H]==}.H

Usage: gsnd -c 1 2 3 -- powerset.ps gives output

[]
[3]
[2]
[3 2]
[1]
[3 1]
[2 1]
[3 2 1]

Un-tokenized version:

count /l exch def
0 1 2 l exp 1 sub{
    /n exch def
    [
    0 1 l 1 sub{
        n 2 mod 1 eq{
            counttomark add index 
        }{
            pop
        }ifelse
      /n n -1 bitshift def
    }for
    ] ==
}for