You came back from grocery shopping.   After putting away all the goods, you are left with a pile of plastic bags, which you want to save for later use, so you take one bag and stuff all the others into it, and throw it under the sink.   In doing so, you realize that there are various ways of nesting the bags, with all bags viewed as identical.

If we use a matching pair of parentheses to represent a bag, the ways are:

For 1 bag, there's one way:

 ()	<- a bag

for 2 bags, there's one way:

 (())	<- one bag in another

for 3 bags, there are two:

 ((())) <- 3 bags nested Russian doll style
 (()()) <- 2 bags side by side, inside the third

for 4 bags, four:

 (()()())
 ((())())
 ((()()))
 (((())))

Note that because all bags are identical, the two 4-bag strings ((())()) and (()(())) represent the same configuration.

It's easy to see that each configuration for n bags represents a n-node rooted tree, where a bag is a tree node, and a bag with its content forms a subtree. The outermost bag is the tree root. Number of configurations for given n is given by OEIS A81.



Task
 
Write a program that, when given n, enumerates all ways of nesting n bags.   You can use the parentheses notation above, or any tree representation that's unambiguous and preferably intuitive.

This task asks for enumeration of trees only; for counting solutions without enumeration, that OEIS page lists various formulas, but that's not encouraged by this task, especially if implementing it would significantly increase code size.

As an example output, run 5 bags.   There should be 9 ways.




with javascript_semantics
atom t0 = time()
sequence list = {1},
         offset = repeat(0,32)
         offset[1..2] = 1
 
function show(integer t, l)
    string res = repeat('?',l)
    integer level = 0
    for i=l to 1 by -1 do
        integer r2 = remainder(t,2)
        res[i] = "[}(]{)"[mod(level-r2,6)+1]
        level += r2*4-2
        t = floor(t/2)
    end for
    if level!=0 then ?9/0 end if
    return res
end function
 
procedure listTrees(integer n)
    for i:=offset[n+1]+1 to offset[n+2] do
        printf(1,"%s\n",{show(list[i], n*2)})
    end for
end procedure
 
procedure assemble(atom t, integer n, sl, pos, rem)
--
-- assemble tree from subtrees
--  t:   assembled parts so far
--  n:   length of tree we want to make
--  sl:  length of subtree we are looking at
--  pos: offset of subtree we are looking at
--  rem: remaining length to be put together
--
    if rem == 0 then
        list = append(list, t*2+1)
    else
        if sl>rem then -- need smaller sub-trees
            sl = rem
            pos = offset[sl+1]
        elsif pos>=offset[sl+2] then
            -- used up sl-trees, try smaller ones
            if sl == 1 then return end if
            pos = offset[sl]
            sl -= 1
        end if
 
        atom u = or_bits(t*power(2,2*sl),list[pos+1])
        assemble(u, n, sl, pos, rem-sl)
        assemble(t, n, sl, pos+1, rem)
    end if
end procedure
 
procedure mktrees(integer n)
    if offset[n+2]=0 then
        if n>0 then
            mktrees(n - 1)
        end if
        assemble(0, n, n-1, offset[n], n-1)
        offset[n+2] = length(list)
    end if
end procedure
 
procedure main(integer n)
    mktrees(n)
    atom nt = offset[n+2]-offset[n+1],
         td = time()-t0
    string e = iff(td>0.1?" ("&elapsed(td)&")":"")
    printf(1,"Number of %d-trees: %,d%s\n", {n, nt, e})
    if n<=5 then listTrees(n) end if
end procedure
for i=0 to iff(platform()=JS?12:20) do
    main(i)
end for
