28
\$\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

47 Answers 47

1
2
1
\$\begingroup\$

Thunno 2, 3 bytes

ʠ¶j

Try it online!

Explanation

ʠ¶j  # Implicit input
ʠ    # Take the powerset
 ¶j  # Join on newlines
     # Implicit output
\$\endgroup\$
1
\$\begingroup\$

Nekomata, 1 byte

S

Attempt This Online!

S finds a subset of a list.

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

\$\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\$
0
\$\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\$
1
  • \$\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, 2016 at 22:33
0
\$\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\$
0
\$\begingroup\$

Mathematica, 51

More cheating:

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

Use with @{1,2,3}.

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

Matlab (46)

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

  • the input must be of the form [% % % ..] where % is a number
\$\endgroup\$
0
\$\begingroup\$

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

Japt -R, 5 bytes

à i[]

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Beat you to it! :p Also, note the (unnecessary) requirement of each element being on its own line. \$\endgroup\$
    – Shaggy
    Jan 4, 2019 at 16:17
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Python 2, 74 bytes

def f(x):
    for i in reduce(lambda s,e:s+[i+[e] for i in s],x,[[]]):print i
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

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!

\$\endgroup\$
0
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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