List rooted trees

List rooted trees is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

J

There ought to be a more elegant way of doing this:

<lang J>incr=:3 :0

r=.
for_bag.y do.
  in=.>bag
  r=. r,<a:,in
  for_j.in i. ~.in do.
    for_more. incr j { in do.
      r=. r,< /:~ more j} in
    end.
  end.
end.
~.r

)

disp=: ([:;<@('(',;,')'"_)"0) L:1^:(0<L.)^:_"0</lang>

Here, we use boxes to represent bags, and a: is an empty box... er... bag. Each use of incr adds a new bag in each of the distinct possible ways.

We actually overdo that slightly - finding all the distinct "one more bag" possibilities for each of our argument cases, and then eliminate duplicates because sometimes adding a bag in one place in one configuration does the same thing as adding a bag in a different place for a different configuration. This deduping requires a certain amount of normalization (at each level we define a canonical order).

Finally, we use disp to convert our tree structures to the desired "parenthesis" notation.

Required example:

<lang J> disp incr^:4 a: (()()()()) (()()(())) ((())(())) (()(()())) (()((()))) ((()()())) ((()(()))) (((()()))) ((((()))))</lang>

Python

<lang python>def bags(n,cache={}): if not n: return [(0, "")]

upto = sum([bags(x) for x in range(n-1, 0, -1)], []) return [(c+1, '('+s+')') for c,s in bagchain((0, ""), n-1, upto)]

def bagchain(x, n, bb, start=0): if not n: return [x]

out = [] for i in range(start, len(bb)): c,s = bb[i] if c <= n: out += bagchain((x[0] + c, x[1] + s), n-c, bb, i) return out

1. Maybe this lessens eye strain. Maybe not.

def replace_brackets(s): depth,out = 0,[] for c in s: if c == '(': out.append("([{"[depth%3]) depth += 1 else: depth -= 1 out.append(")]}"[depth%3]) return "".join(out)

for x in bags(5): print(replace_brackets(x[1]))</lang>

Output:

([{([])}])
([{()()}])
([{()}{}])
([{}{}{}])
([{()}][])
([{}{}][])
([{}][{}])
([{}][][])
([][][][])