Skip to main content
added 774 characters in body
Source Link
ovs
  • 61.2k
  • 3
  • 49
  • 164

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)] 

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!

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)] 
Source Link
ovs
  • 61.2k
  • 3
  • 49
  • 164

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!