20
\$\begingroup\$

Given a non-negative integer n, print the result of P(P(...P({}))), where the number of P's is n (P is the power set function).

0 => {}
1 => P({})
2 => P(P({}))
3 => P(P(P({})))
n => P(f(n-1))
input   result
0       {}
1       {{}}
2       {{},{{}}}
3       {{},{{}},{{{}}},{{},{{}}}}
...

The result should only contain parentheses/brackets/braces and commas, spaces and newlines are allowed.

\$\endgroup\$
7
  • 15
    \$\begingroup\$ Welcome to Code Golf, and nice first question. I'd recommend sticking to our standard I/O rules for code golf, rather than requiring the output using {}, because it means answers have to use a significant amount of bytes in converting their output to the required form. For future reference, we strongly recommend you first post your challenge ideas in the Sandbox to get feedback like this before you post them to the main site. \$\endgroup\$
    – pxeger
    Jun 10 at 9:26
  • 8
    \$\begingroup\$ Also, I assume the output be in any order? For example, for input 2, both {{{}},{}} and {{},{{}}} are ok? And can the output contain duplicates, e.g. {{{}},{},{}}? \$\endgroup\$
    – pxeger
    Jun 10 at 9:27
  • 3
    \$\begingroup\$ I would also look at the sequence rules (as this is extracting from the sequence of repeated applications). \$\endgroup\$ Jun 10 at 10:25
  • 2
    \$\begingroup\$ @A.Rex Maybe the rule pxeger was really thinking about was the one to rule them all: please avoid cumbersome I/O formats. \$\endgroup\$
    – Arnauld
    Jun 11 at 9:23
  • 1
    \$\begingroup\$ @A.Rex well the ideal output format would be as any nested list kind of structure, not necessarily that string \$\endgroup\$
    – pxeger
    Jun 11 at 12:16

16 Answers 16

8
\$\begingroup\$

Jelly, 3 bytes

ŒP¡

Attempt This Online!

Using standard I/O rules; takes input from STDIN

Explanation:

  ¡         repeatedly apply
ŒP           the power set
             to nothing
              which defaults to 0
               which is turned into the range [1..0]
                which is []

If you insist on the {{},{{}}} formatting:

Jelly, 12 bytes

ŒP¡ŒṘ“[{]}”y

Attempt This Online!

This could probably be shorter, but I'm not too interested in golfing boring formatting code.

Explanation:

ŒP¡ŒṘ“[{]}”y
  ¡                 repeatedly apply
ŒP                   the power set
   ŒṘ               convert to string representation
            y       translate
     “[{]}”          square brackets to curly braces
\$\endgroup\$
1
8
\$\begingroup\$

Burlesque, 8 bytes

{}1qR@C~

Try it online!

{}   # Empty block
1    # Continuation takes top 1 elements of stack
qR@  # Quoted powerset
C~   # Continuation forever, printing all powersets

If you insist on getting a particular N

Burlesque, 11 bytes

{}1qR@C~j!!

Try it online!

j!! # Reorder stack, get from block

And if you insist on comma-separated formatting add 8 bytes for

up' ',r~
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Fixed, though the main block is not affected. \$\endgroup\$ Jun 10 at 14:18
6
\$\begingroup\$

Wolfram Language (Mathematica), 19 bytes

Nest[Subsets,{},#]&

Try it online!

In the notebook interface, the results are printed without spaces. But in TIO or the text-based interface, spaces are automatically added.

\$\endgroup\$
6
\$\begingroup\$

Vyxal, 4 bytes

or 12

¾?(ṗ

Explanation

¾?(ṗ
¾     Global array, empty at the start
 ?    Get input n
  (   Start loop n times
   ṗ  Powerset

Try it Online!

12 bytes with the curly braces formatting:

(thanks to @lyxal)

¾?(ṗ)S¾S‛{}Ŀ
¾?(ṗ)S¾S‛{}Ŀ
¾?(ṗ)          The boring stuff
     S         Stringify the power-setted list
      ¾        Empty list -> `[]`
       ‛{}     Curly braces
          Ŀ    Transliterate, replace `[]` with the curly braces

The P prints the list with its python representation. Try it online!

\$\endgroup\$
6
\$\begingroup\$

Python, 96 bytes

from itertools import*
f=lambda n:n and(chain(*(combinations(f(n-1),r)for r in range(n+1))))or()

Attempt This Online!

\$\endgroup\$
5
\$\begingroup\$

Haskell, 53 bytes

f=(!!)$iterate(\l->init l++[','|l/="{}"]++l++"}")"{}"

Try it online!

My first golf. Nothing particularly clever, uses the Fokker trick to deal with the base case.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Jun 11 at 22:35
  • \$\begingroup\$ I don't think this does the task, unfortunately. The output for taking power set n=5 times should be enormous, larger than roughly doubling the length of the string each time. It looks like you're outputting ordinals, similar to this old challenge. \$\endgroup\$
    – xnor
    Jun 17 at 9:15
4
\$\begingroup\$

Pyth, 3 or 17 11 bytes

yFY

Try it online!

F - Repeat Q times, where Q is the implicit input:

y - powerset of

Y - empty list

With formatting

X`yFYQ"[]}{

Try it online!

X..."[]}{ - convert each occurrence of [ to { and each occurrence of ] to }

\$\endgroup\$
3
\$\begingroup\$

05AB1E (legacy), 4 or 17 bytes

Regular I/O using [] instead of {} and spaces after the commas would be 4 bytes:

¯IFæ

Try it online or verify the first few test cases.

Strict I/O format is 17 bytes:

¯IFæ}"ÿ"„[]„{}‡ðK

Try it online or verify the first few test cases.

Explanation:

"ÿ" on lists only works in the legacy version of 05AB1E (built in Python), and unfortunately not in the new 05AB1E version (built in Elixir). I'm not sure how to do this challenge in the new version of 05AB1E, which lacks any form of toString builtin on lists..

¯        # Push an empty list: []
 IF      # Loop the input amount of times:
   æ     #  Pop the current list, and push its powerset
         # (after the loop, the result is output implicitly)

¯IFæ     # Same as above
  }      # Close the loop
   "ÿ"   # Convert the (nested) list to a string
„[]„{}‡  # Transliterate all "[" to "{" and "]" to "}"
ðK       # Remove all spaces
         # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES10), 95 bytes

Assuming a strict output format:

f=(n,a=[])=>n?f(n-1,a.reduce((a,x)=>a.flatMap(y=>[y,[...y,x]]),[[]])):(g=a=>`{${a.map(g)}}`)(a)

Try it online!


JavaScript (ES10), 71 bytes

Returning an array of arrays:

f=(n,a=[])=>n?f(n-1,a.reduce((a,x)=>a.flatMap(y=>[y,[...y,x]]),[[]])):a

Try it online!

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

Factor + math.combinatorics, 72 bytes

[ { } [ all-subsets ] repeat unparse " "without "}{""},{"replace write ]

Try it online!

As written.


Factor + math.combinatorics, 30 bytes

[ { } [ all-subsets ] repeat ]

Try it online!

With standard I/O rules.

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

C (gcc), 206 bytes

#define P putchar
f(i,s,c){P(123);for(s=0;i;++s,i>>=1)if(i&1){f(s);if(i>1)P(44);}P(125);}s,i;main(c,v)char**v;{sscanf(v[1],"%d",&c);for(s=!!c--;c>0;--c)s=1<<s;P(123);for(;i<s;){f(i++);if(s>i)P(44);}P(125);}

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can shave a few bytes: for(;i<s;){f(i++);if(s>i)P(44);} --> for(;i<s;)f(i++),(s>i)&&P(44); the same trick can be used to shorten if(i&1){f(s);if(i>1)P(44);} \$\endgroup\$
    – Matteo C.
    Jun 10 at 20:17
  • \$\begingroup\$ Building on @MatteoC. 178 bytes \$\endgroup\$
    – ceilingcat
    Jun 13 at 6:13
  • 2
    \$\begingroup\$ It looks like you're not using the 3rd parameter in f, so you can get rid of it for -2 bytes \$\endgroup\$ Jun 13 at 16:53
  • \$\begingroup\$ Since this has undefined behaviour for n > 5 maybe it's fine to do it like this for 166 bytes, which wouldn't work for n > 9 anyway \$\endgroup\$ Jun 13 at 18:04
1
\$\begingroup\$

05AB1E, 3 bytes

Ties pxeger's Jelly answer and math junkie's Pyth answer for #1.

ćFæ

Try it online! Takes input as a singleton list, and outputs with square brackets.

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

Charcoal, 26 bytes

F⊕N≔EX²Lυ⪫{}⪫Φυ﹪÷κX²ν²,υ⊟υ

Try it online! Link is to verbose version of code. Extremely inefficient; do not try n=4 unless you have a lot of patience (will time out on TIO). Explanation:

F⊕N

Repeat n+1 times...

≔EX²Lυ⪫{}⪫Φυ﹪÷κX²ν²,υ

... replace the predefined empty list with its formatted powerset.

⊟υ

Output the last element.

21 bytes using Python list formatting:

FN≔EX²LυΦυ﹪÷κX²ν²υ⭆¹υ

Try it online! Link is to verbose version of code. Explanation:

FN

Repeat n times...

≔EX²LυΦυ﹪÷κX²ν²υ

... replace the predefined empty list with its powerset.

⭆¹υ

Pretty-print the list.

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

R, 205 bytes

\(n,z=paste0,b=\(x)z('{',x,'}'),p=\(x,e=el(strsplit(x,',')),l=lapply(e,\(i)c(i,NA)),g=do.call(expand.grid,l),d=\(v)z(na.omit(v),collapse=','),a=apply(g,1,d))d(b(a))){s='';for(i in seq_len(n)){s=p(s)};b(s)}

Attempt This Online!

A naive implementation of powerset for comma-delimited strings in R, using seq_len instead of 1:n to handle the n = 0 case correctly.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ @evanstar3 you proposed an edit to change this to a C-language implementation that I believe is your own. I believe that implementation should be an answer so you receive due credit. \$\endgroup\$
    – Cong Chen
    Jun 10 at 19:52
0
\$\begingroup\$

APL(Dyalog Unicode), 34 bytes SBCS

{⎕json{⌿∘⍵¨↓⌽⍉2⊥⍣¯1⊢¯1+⍳2*≢⍵}⍣⍵⊢⍬}

Try it on APLgolf!

Marked as community wiki because the power set function has been taken from APLCart.

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

BQN, 17 bytes

{(⥊(↕2˘)/¨<)⍟𝕩⟨⟩}

Try it here!

Powerset composed x times on empty set.


BQN, 42 bytes

{{'⟨':'{';'⟩':'}';𝕩}¨•Repr(⥊(↕2˘)/¨<)⍟𝕩⟨⟩}

Try it here!

Strictly formatted variant.

If ⟨⟩ count as valid brackets, then simply remove {'⟨':'{';'⟩':'}';𝕩}¨ for a 22-byte solution.

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