Generate all groupings

Question

Let's define a grouping as a flat list, which is either:

• just 0
• 2 groupings followed by the literal integer 2
• 3 groupings followed by 3
• 4 groupings followed by 4
• etc. (for all integers \$ \ge 2 \$)

Note that 1 is not included in this definition, because otherwise groupings could be infinite.

For example, these are valid groupings:

• 0
• 0 0 2
• 0 0 0 3
• 0 0 0 2 2
• 0 0 0 0 0 2 3 0 0 0 4 2 0 2

If it helps, here is a more visual representation of the last two groupings above, using parentheses to show how they're constructed:

(0 ((0 0) 2) 2)
((0 ((0 0 (0 0 2) 3) 0 0 0 4) 2) 0 2)

Task

Given a positive integer n, output all possible groupings which contain exactly n 0s.

For example, for n = 3, there are 3 possible groupings:

• 0 0 0 3
• 0 0 0 2 2
• 0 0 2 0 2

Rules

• Outputs may be in any order, but duplicate outputs are not allowed.
• You may use any standard I/O method
• Standard loopholes are forbidden
• This is code-golf, so the shortest code in bytes wins

Test cases

input -> outputs
1 -> [0]
2 -> [0 0 2]
3 -> [0 0 0 2 2], [0 0 0 3], [0 0 2 0 2]
4 -> [0 0 0 0 2 2 2], [0 0 0 0 2 3], [0 0 0 0 3 2], [0 0 0 0 4], [0 0 0 2 0 2 2], [0 0 0 2 0 3], [0 0 0 2 2 0 2], [0 0 0 3 0 2], [0 0 2 0 0 2 2], [0 0 2 0 0 3], [0 0 2 0 2 0 2]
5 -> [0 0 0 0 0 2 2 2 2], [0 0 0 0 0 2 2 3], [0 0 0 0 0 2 3 2], [0 0 0 0 0 2 4], [0 0 0 0 0 3 2 2], [0 0 0 0 0 3 3], [0 0 0 0 0 4 2], [0 0 0 0 0 5], [0 0 0 0 2 0 2 2 2], [0 0 0 0 2 0 2 3], [0 0 0 0 2 0 3 2], [0 0 0 0 2 0 4], [0 0 0 0 2 2 0 2 2], [0 0 0 0 2 2 0 3], [0 0 0 0 2 2 2 0 2], [0 0 0 0 2 3 0 2], [0 0 0 0 3 0 2 2], [0 0 0 0 3 0 3], [0 0 0 0 3 2 0 2], [0 0 0 0 4 0 2], [0 0 0 2 0 0 2 2 2], [0 0 0 2 0 0 2 3], [0 0 0 2 0 0 3 2], [0 0 0 2 0 0 4], [0 0 0 2 0 2 0 2 2], [0 0 0 2 0 2 0 3], [0 0 0 2 0 2 2 0 2], [0 0 0 2 0 3 0 2], [0 0 0 2 2 0 0 2 2], [0 0 0 2 2 0 0 3], [0 0 0 2 2 0 2 0 2], [0 0 0 3 0 0 2 2], [0 0 0 3 0 0 3], [0 0 0 3 0 2 0 2], [0 0 2 0 0 0 2 2 2], [0 0 2 0 0 0 2 3], [0 0 2 0 0 0 3 2], [0 0 2 0 0 0 4], [0 0 2 0 0 2 0 2 2], [0 0 2 0 0 2 0 3], [0 0 2 0 0 2 2 0 2], [0 0 2 0 0 3 0 2], [0 0 2 0 2 0 0 2 2], [0 0 2 0 2 0 0 3], [0 0 2 0 2 0 2 0 2]
6 -> [0 0 0 0 0 0 2 2 2 2 2], [0 0 0 0 0 0 2 2 2 3], [0 0 0 0 0 0 2 2 3 2], [0 0 0 0 0 0 2 2 4], [0 0 0 0 0 0 2 3 2 2], [0 0 0 0 0 0 2 3 3], [0 0 0 0 0 0 2 4 2], [0 0 0 0 0 0 2 5], [0 0 0 0 0 0 3 2 2 2], [0 0 0 0 0 0 3 2 3], [0 0 0 0 0 0 3 3 2], [0 0 0 0 0 0 3 4], [0 0 0 0 0 0 4 2 2], [0 0 0 0 0 0 4 3], [0 0 0 0 0 0 5 2], [0 0 0 0 0 0 6], [0 0 0 0 0 2 0 2 2 2 2], [0 0 0 0 0 2 0 2 2 3], [0 0 0 0 0 2 0 2 3 2], [0 0 0 0 0 2 0 2 4], [0 0 0 0 0 2 0 3 2 2], [0 0 0 0 0 2 0 3 3], [0 0 0 0 0 2 0 4 2], [0 0 0 0 0 2 0 5], [0 0 0 0 0 2 2 0 2 2 2], [0 0 0 0 0 2 2 0 2 3], [0 0 0 0 0 2 2 0 3 2], [0 0 0 0 0 2 2 0 4], [0 0 0 0 0 2 2 2 0 2 2], [0 0 0 0 0 2 2 2 0 3], [0 0 0 0 0 2 2 2 2 0 2], [0 0 0 0 0 2 2 3 0 2], [0 0 0 0 0 2 3 0 2 2], [0 0 0 0 0 2 3 0 3], [0 0 0 0 0 2 3 2 0 2], [0 0 0 0 0 2 4 0 2], [0 0 0 0 0 3 0 2 2 2], [0 0 0 0 0 3 0 2 3], [0 0 0 0 0 3 0 3 2], [0 0 0 0 0 3 0 4], [0 0 0 0 0 3 2 0 2 2], [0 0 0 0 0 3 2 0 3], [0 0 0 0 0 3 2 2 0 2], [0 0 0 0 0 3 3 0 2], [0 0 0 0 0 4 0 2 2], [0 0 0 0 0 4 0 3], [0 0 0 0 0 4 2 0 2], [0 0 0 0 0 5 0 2], [0 0 0 0 2 0 0 2 2 2 2], [0 0 0 0 2 0 0 2 2 3], [0 0 0 0 2 0 0 2 3 2], [0 0 0 0 2 0 0 2 4], [0 0 0 0 2 0 0 3 2 2], [0 0 0 0 2 0 0 3 3], [0 0 0 0 2 0 0 4 2], [0 0 0 0 2 0 0 5], [0 0 0 0 2 0 2 0 2 2 2], [0 0 0 0 2 0 2 0 2 3], [0 0 0 0 2 0 2 0 3 2], [0 0 0 0 2 0 2 0 4], [0 0 0 0 2 0 2 2 0 2 2], [0 0 0 0 2 0 2 2 0 3], [0 0 0 0 2 0 2 2 2 0 2], [0 0 0 0 2 0 2 3 0 2], [0 0 0 0 2 0 3 0 2 2], [0 0 0 0 2 0 3 0 3], [0 0 0 0 2 0 3 2 0 2], [0 0 0 0 2 0 4 0 2], [0 0 0 0 2 2 0 0 2 2 2], [0 0 0 0 2 2 0 0 2 3], [0 0 0 0 2 2 0 0 3 2], [0 0 0 0 2 2 0 0 4], [0 0 0 0 2 2 0 2 0 2 2], [0 0 0 0 2 2 0 2 0 3], [0 0 0 0 2 2 0 2 2 0 2], [0 0 0 0 2 2 0 3 0 2], [0 0 0 0 2 2 2 0 0 2 2], [0 0 0 0 2 2 2 0 0 3], [0 0 0 0 2 2 2 0 2 0 2], [0 0 0 0 2 3 0 0 2 2], [0 0 0 0 2 3 0 0 3], [0 0 0 0 2 3 0 2 0 2], [0 0 0 0 3 0 0 2 2 2], [0 0 0 0 3 0 0 2 3], [0 0 0 0 3 0 0 3 2], [0 0 0 0 3 0 0 4], [0 0 0 0 3 0 2 0 2 2], [0 0 0 0 3 0 2 0 3], [0 0 0 0 3 0 2 2 0 2], [0 0 0 0 3 0 3 0 2], [0 0 0 0 3 2 0 0 2 2], [0 0 0 0 3 2 0 0 3], [0 0 0 0 3 2 0 2 0 2], [0 0 0 0 4 0 0 2 2], [0 0 0 0 4 0 0 3], [0 0 0 0 4 0 2 0 2], [0 0 0 2 0 0 0 2 2 2 2], [0 0 0 2 0 0 0 2 2 3], [0 0 0 2 0 0 0 2 3 2], [0 0 0 2 0 0 0 2 4], [0 0 0 2 0 0 0 3 2 2], [0 0 0 2 0 0 0 3 3], [0 0 0 2 0 0 0 4 2], [0 0 0 2 0 0 0 5], [0 0 0 2 0 0 2 0 2 2 2], [0 0 0 2 0 0 2 0 2 3], [0 0 0 2 0 0 2 0 3 2], [0 0 0 2 0 0 2 0 4], [0 0 0 2 0 0 2 2 0 2 2], [0 0 0 2 0 0 2 2 0 3], [0 0 0 2 0 0 2 2 2 0 2], [0 0 0 2 0 0 2 3 0 2], [0 0 0 2 0 0 3 0 2 2], [0 0 0 2 0 0 3 0 3], [0 0 0 2 0 0 3 2 0 2], [0 0 0 2 0 0 4 0 2], [0 0 0 2 0 2 0 0 2 2 2], [0 0 0 2 0 2 0 0 2 3], [0 0 0 2 0 2 0 0 3 2], [0 0 0 2 0 2 0 0 4], [0 0 0 2 0 2 0 2 0 2 2], [0 0 0 2 0 2 0 2 0 3], [0 0 0 2 0 2 0 2 2 0 2], [0 0 0 2 0 2 0 3 0 2], [0 0 0 2 0 2 2 0 0 2 2], [0 0 0 2 0 2 2 0 0 3], [0 0 0 2 0 2 2 0 2 0 2], [0 0 0 2 0 3 0 0 2 2], [0 0 0 2 0 3 0 0 3], [0 0 0 2 0 3 0 2 0 2], [0 0 0 2 2 0 0 0 2 2 2], [0 0 0 2 2 0 0 0 2 3], [0 0 0 2 2 0 0 0 3 2], [0 0 0 2 2 0 0 0 4], [0 0 0 2 2 0 0 2 0 2 2], [0 0 0 2 2 0 0 2 0 3], [0 0 0 2 2 0 0 2 2 0 2], [0 0 0 2 2 0 0 3 0 2], [0 0 0 2 2 0 2 0 0 2 2], [0 0 0 2 2 0 2 0 0 3], [0 0 0 2 2 0 2 0 2 0 2], [0 0 0 3 0 0 0 2 2 2], [0 0 0 3 0 0 0 2 3], [0 0 0 3 0 0 0 3 2], [0 0 0 3 0 0 0 4], [0 0 0 3 0 0 2 0 2 2], [0 0 0 3 0 0 2 0 3], [0 0 0 3 0 0 2 2 0 2], [0 0 0 3 0 0 3 0 2], [0 0 0 3 0 2 0 0 2 2], [0 0 0 3 0 2 0 0 3], [0 0 0 3 0 2 0 2 0 2], [0 0 2 0 0 0 0 2 2 2 2], [0 0 2 0 0 0 0 2 2 3], [0 0 2 0 0 0 0 2 3 2], [0 0 2 0 0 0 0 2 4], [0 0 2 0 0 0 0 3 2 2], [0 0 2 0 0 0 0 3 3], [0 0 2 0 0 0 0 4 2], [0 0 2 0 0 0 0 5], [0 0 2 0 0 0 2 0 2 2 2], [0 0 2 0 0 0 2 0 2 3], [0 0 2 0 0 0 2 0 3 2], [0 0 2 0 0 0 2 0 4], [0 0 2 0 0 0 2 2 0 2 2], [0 0 2 0 0 0 2 2 0 3], [0 0 2 0 0 0 2 2 2 0 2], [0 0 2 0 0 0 2 3 0 2], [0 0 2 0 0 0 3 0 2 2], [0 0 2 0 0 0 3 0 3], [0 0 2 0 0 0 3 2 0 2], [0 0 2 0 0 0 4 0 2], [0 0 2 0 0 2 0 0 2 2 2], [0 0 2 0 0 2 0 0 2 3], [0 0 2 0 0 2 0 0 3 2], [0 0 2 0 0 2 0 0 4], [0 0 2 0 0 2 0 2 0 2 2], [0 0 2 0 0 2 0 2 0 3], [0 0 2 0 0 2 0 2 2 0 2], [0 0 2 0 0 2 0 3 0 2], [0 0 2 0 0 2 2 0 0 2 2], [0 0 2 0 0 2 2 0 0 3], [0 0 2 0 0 2 2 0 2 0 2], [0 0 2 0 0 3 0 0 2 2], [0 0 2 0 0 3 0 0 3], [0 0 2 0 0 3 0 2 0 2], [0 0 2 0 2 0 0 0 2 2 2], [0 0 2 0 2 0 0 0 2 3], [0 0 2 0 2 0 0 0 3 2], [0 0 2 0 2 0 0 0 4], [0 0 2 0 2 0 0 2 0 2 2], [0 0 2 0 2 0 0 2 0 3], [0 0 2 0 2 0 0 2 2 0 2], [0 0 2 0 2 0 0 3 0 2], [0 0 2 0 2 0 2 0 0 2 2], [0 0 2 0 2 0 2 0 0 3], [0 0 2 0 2 0 2 0 2 0 2]

Answer 1

Haskell, 59 bytes

Returns a list of groupings in lexicographic order.

(!0)
0!1=[[]]
n!s=[k:g|k<-[0^n..s],k/=1,g<-(n-0^k)!(s+1-k)]

Try it online!

The possible groupings can be constructed from left to right if you keep track of two values: the remaining number of 0s to place, and the number of currently open groupings. When all 0s are placed and there is a single open grouping, we have constructed a valid output.

This is implemented by the function (!) which takes the number of 0s as a left argument n and the open groupings as s. At each step we can insert a 0 if n>0 and any integer in [2..s] to close multiple open groupings.

-- main function: (!) with 0 open groupings
(!0)
-- base case: no more 0s to place, a single grouping left
0!1=[[]]
-- k is the number to insert
-- 0^n == if n==0 then 1 else 0
n!s=[k:g|k<-[0^n..s],k/=1,g<-(n-0^k)!(s+1-k)]

Answer 2

Wolfram Language (Mathematica), version 12.3.1, 44 bytes

Groupings[#,2~Range~#,Length/@#~Level~All&]&

Try it online!

Yes, Mathematica has a built-in for groupings.

But the version on TIO (Mathematica 12.0.1) gives the wrong result for input 1. The version I'm using (Mathematica 12.3.1) works correctly.

Answer 3

JavaScript (V8),  77  76 bytes

Prints all groupings as comma-separated strings.

f=(n,s=0,g=0,h=k=>k|n>1?f(k?h(k-1)|n:n+--k,s+[,k+1],g-k):!g&&print(s))=>h(g)

Try it online!

Commented

f = (                  // f is a recursive function taking:
  n,                   //   n = input
  s = 0,               //   s = output 'string' (initially the number 0)
  g = 0,               //   g = number of groupings - 1
  h = k =>             //   h = helper recursive function taking a counter k
    k | n > 1 ?        //     if k is not equal to 0 or n is greater than 1:
      f(               //       recursive call to f:
        k ?            //         if k is not equal to 0:
          h(k - 1)     //           do a recursive call to h with k - 1
          | n          //           and pass n unchanged (*)
        :              //         else:
          n + --k,     //           set k = -1 and decrement n
        s + [, k + 1], //         append a comma followed by k + 1 to s
        g - k          //         subtract k from g
                       //         (this actually increments g if k = -1)
      )                //       end of recursive call
    :                  //     else:
      !g && print(s)   //       print s if g = 0
) => h(g)              // initial call to h with k = g

(*) This relies on the fact that h() will always eventually return a zero'ish value. And that's why we use !g && print(s) rather than g || print(s).

Answer 4

Charcoal, 47 bytes

Ｎθ⊞υ⟦⁰⟧ＦυＦ⁺…⁰‹№ι⁰θ…·²⁻ＬιΣι⊞υ⁺ι⟦κ⟧ＩΦυ⁼⁼№ι⁰θ⁻ＬιΣι

Try it online! Link is to verbose version of code. Explanation: A simplification of @ovs's method, where the number of 0s to place is simply the desired number of 0s minus the current number of 0s, and the number of open groupings is the length minus the sum.

Ｎθ

Input the desired number of 0s.

⊞υ⟦⁰⟧Ｆυ

Start a breadth first search with a single 0. (I can't use an empty list because Sum([]) isn't 0 in Charcoal.)

Ｆ⁺…⁰‹№ι⁰θ…·²⁻ＬιΣι

Loop over the concatenation of two ranges, one from 0 to whether more 0s are needed (so either an empty range or a range containing just 0), one from 2 to the difference between the length and the sum inclusive.

⊞υ⁺ι⟦κ⟧

Append the value to the grouping and push it to the search list.

ＩΦυ⁼⁼№ι⁰θ⁻ＬιΣι

Output those groupings with one grouping and the correct number of 0s.

Answer 5

Core Maude, 209 + 15 = 224 bytes

mod G is inc LIST{Nat}*(op size to{_]). ops({_})([_]): Nat ~> Nat . var A B
N :[Nat]. eq{N}=[N]N . eq 0 1 = 0 . eq[0]= nil . eq[s N]= 0[N]. crl A B N =>
A{A]B s sd(N,{A])if{A]> 1 /\{A]< N /\ A B =[{A B]]. endm

To get the list of groupings for \$n\$, run the following Maude command with the \$G\$ module loaded.

search{𝑛}=>* A .

The groupings will be the listed assignments to \$A\$. So, for example, for \$n = 3\$ run

search{3}=>* A .

(The bytes of this command — minus the bytes to specify \$n\$ — have been included in the total.)

Example Session

Maude> search{1}=>* A .
search in G : {1} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 4 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0

No more solutions.
states: 1  rewrites: 15 in 0ms cpu (0ms real) (~ rewrites/second)
Maude> search{2}=>* A .
search in G : {2} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 4 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 2

No more solutions.
states: 1  rewrites: 128 in 0ms cpu (0ms real) (~ rewrites/second)
Maude> search{3}=>* A .
search in G : {3} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 5 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 3

Solution 2 (state 1)
states: 2  rewrites: 181 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 2 0 2

Solution 3 (state 2)
states: 3  rewrites: 218 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 2 2

No more solutions.
states: 3  rewrites: 1467 in 1ms cpu (1ms real) (1467000 rewrites/second)
Maude> search{4}=>* A .
search in G : {4} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 6 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 0 4

-- SNIP --

Solution 11 (state 10)
states: 11  rewrites: 4520 in 3ms cpu (3ms real) (1506666 rewrites/second)
A --> 0 0 0 0 2 2 2

No more solutions.
states: 11  rewrites: 15508 in 12ms cpu (12ms real) (1292333 rewrites/second)
Maude> search{5}=>* A .
search in G : {5} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 7 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 0 0 5

-- SNIP --

Solution 45 (state 44)
states: 45  rewrites: 72386 in 42ms cpu (41ms real) (1723476 rewrites/second)
A --> 0 0 0 0 0 2 2 2 2

No more solutions.
states: 45  rewrites: 149258 in 59ms cpu (58ms real) (2529796 rewrites/second)
Maude> search{6}=>* A .
search in G : {6} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 8 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 0 0 0 6

-- SNIP --

Solution 197 (state 196)
states: 197  rewrites: 853311 in 216ms cpu (215ms real) (3950513 rewrites/second)
A --> 0 0 0 0 0 0 2 2 2 2 2

No more solutions.
states: 197  rewrites: 1340298 in 329ms cpu (328ms real) (4073854 rewrites/second)

Ungolfed

mod G is
    inc LIST{Nat} * (op size to {_]) .

    ops ({_}) ([_]) : Nat ~> Nat .

    var A B N : [Nat] .

    eq {N} = [N] N .
    eq 0 1 = 0 .

    eq [0] = nil .
    eq [s N] = 0 [N] .

    crl A B N => A {A] B s sd(N, {A]) if {A] > 1 /\ {A] < N /\ A B = [{A B]] .
endm

This solution uses Maude's rewriting feature, where Maude will search using a rewrite system to find all solutions to an problem of the form \$t_1 \to_R^* t_2\$, or in this case, \$\{n\} \to_G^* A\$, where \$\to_G^*\$ means zero or more applications of rules in \$G\$, and \$A\$ is a variable (so essentially any term). The single rule picks a run of zeros and groups them, so Maude will explore every way of grouping starting from \$\{n\} \approx_G 0 \; 0 \, \cdots \, 0 \; n\$.

We use odd function names ({_}, [_], and {_]) to take advantage of Maude's odd tokenization rules. {_} creates the initial grouping; [_] produces a list of zeroes; {_] is the renamed size function for lists.

Answer 6

Python, 100 bytes

f=lambda n:[k+j+R for i in range(1,n)for*j,J in f(i)for k in f(n-i)for R in[[J,2],[J+1]][:i]]or[[0]]

Attempt This Online!

How?

One big recursive list comprehension. Conceptually: Cut off the tree's lefttmost branch (from the root node) and do recursion on both bits. Technicality: The right bit is the original tree with the left bit removed, while the left bit discards the root branch so as not to violate the no nonbranching nodes requirement. IOW, the left bit hangs one level lower than the right bit. Except when the original tree had only two root branches. Then both hang low.

Answer 7

Curry (PAKCS), 63 bytes

(!0)
0!1=[]
n!s=anyOf[k:n!(s+1-k)|k<-[2..s]]?n>0&>0:(n-1)!(s+1)

Try it online!

Based on ovs's Haskell answer. There are two differences:

• The ^ operator is not supported by the Curry version on TIO.
• An expression in Curry can be non-deterministic, i.e. having multiple values at the same time. Here I define a non-deterministic function f, whose return values are all the possible groupings.

---

Curry (PAKCS), 68 bytes

(([]:iterate g[0])!!)
g a=a++[0,2]
g(a++[b])|b>1=g a++[b]?a++[0,b+1]

Try it online!

Another non-deterministic function that returns all the possible groupings at the same time.

Answer 8

JavaScript (Node.js), 86 84 bytes

f=(n,x=[0],i=0)=>n?x.flatMap((_,j)=>j>i?[]:f(n-!j,[...u=x,j+=!!j],i-j+1)):i-1?[]:[u]

Try it online!

Answer 9

Python3, 205 bytes:

f=lambda x:''.join(f(i)if list==type(i)else'0'for i in x)+str(l:=len(x))*(l>1)
def s(n,c=[]):
 if n:
  for i in[c+[0],*[[],[[0,c]]][j:=len(c)>1],*[[],[[c,0]]][j]]:
   yield from s(n-1,i)
 else:yield f(c)

Try it online!