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

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

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

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

Japt -R, 5 bytes

à i[]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Beat you to it! :p Also, note the (unnecessary) requirement of each element being on its own line. \$\endgroup\$ – Shaggy Jan 4 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\$

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!

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

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

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.