Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
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.
ŒP¡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:
ŒP¡ŒṘ“[{]}”yThis 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
{}1qR@C~
{} # 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
{}1qR@C~j!!
j!! # Reorder stack, get from block
And if you insist on comma-separated formatting add 8 bytes for
up' ',r~
Nest[Subsets,{},#]&
In the notebook interface, the results are printed without spaces. But in TIO or the text-based interface, spaces are automatically added.
or 12
¾?(ṗ
¾?(ṗ
¾ Global array, empty at the start
? Get input n
( Start loop n times
ṗ Powerset
(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!
from itertools import* f=lambda n:n and(chain(*(combinations(f(n-1),r)for r in range(n+1))))or()
f=(!!)$iterate(\l->init l++[','|l/="{}"]++l++"}")"{}"
My first golf. Nothing particularly clever, uses the Fokker trick to deal with the base case.
yFY
F - Repeat Q times, where Q is the implicit input:
y - powerset of
Y - empty list
X`yFYQ"[]}{
X..."[]}{ - convert each occurrence of [ to { and each occurrence of ] to }
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)
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)
Returning an array of arrays:
f=(n,a=[])=>n?f(n-1,a.reduce((a,x)=>a.flatMap(y=>[y,[...y,x]]),[[]])):a
#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);}
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\$
Jun 10 at 20:17
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
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.
Ｆ⊕Ｎ≔ＥＸ²Ｌυ⪫{}⪫Φυ﹪÷κＸ²ν²,υ⊟υ
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:
Ｆ⊕Ｎ
Repeat n+1 times...
≔ＥＸ²Ｌυ⪫{}⪫Φυ﹪÷κＸ²ν²,υ
... replace the predefined empty list with its formatted powerset.
⊟υ
Output the last element.
21 bytes using Python list formatting:
ＦＮ≔ＥＸ²ＬυΦυ﹪÷κＸ²ν²υ⭆¹υ
Try it online! Link is to verbose version of code. Explanation:
ＦＮ
Repeat n times...
≔ＥＸ²ＬυΦυ﹪÷κＸ²ν²υ
... replace the predefined empty list with its powerset.
⭆¹υ
Pretty-print the list.
\(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)}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.
{⎕json{⌿∘⍵¨↓⌽⍉2⊥⍣¯1⊢¯1+⍳2*≢⍵}⍣⍵⊢⍬}
Marked as community wiki because the power set function has been taken from APLCart.
{(⥊(↕2˘)/¨<)⍟𝕩⟨⟩}
Powerset composed x times on empty set.
{{'⟨':'{';'⟩':'}';𝕩}¨•Repr(⥊(↕2˘)/¨<)⍟𝕩⟨⟩}
Strictly formatted variant.
If ⟨⟩ count as valid brackets, then simply remove {'⟨':'{';'⟩':'}';𝕩}¨ for a 22-byte solution.
{}, 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\${{{}},{}}and{{},{{}}}are ok? And can the output contain duplicates, e.g.{{{}},{},{}}? \$\endgroup\$