List rooted trees
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 12 ways.
C
Trees are represented by integers. When written out in binary with LSB first, 1 is opening bracket and 0 is closing. <lang c>#include <stdio.h>
- include <stdlib.h>
typedef unsigned int uint; typedef unsigned long long tree;
- define B(x) (1ULL<<(x))
tree *list = 0; uint cap = 0, len = 0; uint offset[32] = {0, 1, 0};
void append(tree t) { if (len == cap) { cap = cap ? cap*2 : 2; list = realloc(list, cap*sizeof(tree)); } list[len++] = 1 | t<<1; }
void show(tree t, uint len) { for (; len--; t >>= 1) putchar(t&1 ? '(' : ')'); }
void listtrees(uint n) { uint i; for (i = offset[n]; i < offset[n+1]; i++) { show(list[i], n*2); putchar('\n'); } }
/* assemble tree from subtrees n: length of tree we want to make t: assembled parts so far sl: length of subtree we are looking at pos: offset of subtree we are looking at rem: remaining length to be put together
- /
void assemble(uint n, tree t, uint sl, uint pos, uint rem) { if (!rem) { append(t); return; }
if (sl > rem) // need smaller subtrees pos = offset[sl = rem]; else if (pos >= offset[sl + 1]) { // used up sl-trees, try smaller ones if (!--sl) return; pos = offset[sl]; }
assemble(n, t<<(2*sl) | list[pos], sl, pos, rem - sl); assemble(n, t, sl, pos + 1, rem); }
void mktrees(uint n) { if (offset[n + 1]) return; if (n) mktrees(n - 1);
assemble(n, 0, n-1, offset[n-1], n-1); offset[n+1] = len; }
int main(int c, char**v) { int n; if (c < 2 || (n = atoi(v[1])) <= 0 || n > 25) n = 5;
// init 1-tree append(0);
mktrees((uint)n); fprintf(stderr, "Number of %d-trees: %u\n", n, offset[n+1] - offset[n]); listtrees((uint)n);
return 0; }</lang>
- Output:
% ./a.out 5 Number of 5-trees: 9 ((((())))) (((()()))) ((()(()))) ((()()())) (()((()))) (()(()())) ((())(())) (()()(())) (()()()())
D
<lang d>import std.stdio, std.conv;
alias Tree = ulong,
TreeList = Tree[],
Offset = uint[32];
void listTees(in uint n, in ref Offset offset, in TreeList list) nothrow @nogc @safe {
static void show(in Tree t, in uint len) nothrow @nogc @safe {
foreach (immutable i; 0 .. len)
putchar(t & (2 ^^ i) ? '(' : ')');
}
foreach (immutable i; offset[n] .. offset[n + 1]) {
show(list[i], n * 2);
putchar('\n');
}
}
void append(in Tree t, ref TreeList list, ref uint len) pure nothrow @safe {
if (len == list.length)
list.length = list.length ? list.length * 2 : 2;
list[len] = 1 | (t << 1);
len++;
}
/** Assemble tree from subtrees.
Params:
n = length of tree we want to make. t = assembled parts so far. sl = length of subtree we are looking at. pos = offset of subtree we are looking at. rem = remaining length to be put together.
- /
void assemble(in uint n, in Tree t, uint sl, uint pos, in uint rem, in ref Offset offset,
ref TreeList list, ref uint len) pure nothrow @safe {
if (!rem) {
append(t, list, len);
return;
}
if (sl > rem) { // Need smaller subtrees.
sl = rem;
pos = offset[sl];
} else if (pos >= offset[sl + 1]) {
// Used up sl-trees, try smaller ones.
sl--;
if (!sl)
return;
pos = offset[sl];
}
assemble(n, t << (2 * sl) | list[pos], sl, pos, rem - sl, offset, list, len); assemble(n, t, sl, pos + 1, rem, offset, list, len);
}
void makeTrees(in uint n, ref Offset offset,
ref TreeList list, ref uint len) pure nothrow @safe {
if (offset[n + 1])
return;
if (n)
makeTrees(n - 1, offset, list, len);
assemble(n, 0, n - 1, offset[n - 1], n - 1, offset, list, len); offset[n + 1] = len;
}
void main(in string[] args) {
immutable uint n = (args.length == 2) ? args[1].to!uint : 5;
if (n >= 25)
return;
Offset offset; offset[1] = 1;
Tree[] list; uint len = 0;
// Init 1-tree. append(0, list, len);
makeTrees(n, offset, list, len);
stderr.writefln("Number of %d-trees: %u", n, offset[n + 1] - offset[n]);
listTees(n, offset, list);
}</lang>
- Output:
Number of 5-trees: 9 ((((())))) (((()()))) ((()(()))) ((()()())) (()((()))) (()(()())) ((())(())) (()()(())) (()()()())
Haskell
There probably is a nicer way than the following-- <lang haskell>-- break n down into sum of smaller integers parts n = f n 1 where f n x | n == 0 = [[]] | x > n = [] | otherwise = f n (x+1) ++ concatMap (\c->map ((c,x):) (f (n-c*x) (x+1))) [1 .. n`div`x]
-- choose n strings out of a list and join them pick _ [] = [] pick 0 _ = [""] pick n aa@(a:as) = map (a++) (pick (n-1) aa) ++ pick n as
-- pick parts to build a series of subtrees that add up to n-1, then wrap them up trees n = map (\x->"("++x++")") $ concatMap (foldr (prod.build) [""]) (parts (n-1)) where build (c,x) = pick c $ trees x prod aa bb = [ a++b | a<-aa, b<-bb ]
main = mapM_ putStrLn $ trees 5</lang>
- Output:
((((())))) (((()()))) ((()(()))) ((()()())) ((())(())) (()((()))) (()(()())) (()()(())) (()()()())
J
Implementation:
<lang j>root=: 1 1 $ _ incr=: ,/@(,"1 0/ i.@{:@$)
disp=: ('(' , ')' ,~ [: ; [ <@disp"1 0^:(0 < #@]) I.@:=) {.</lang>
Task example:
<lang j> ~.disp&0"1 incr^:4 root (()()()()) ((())()()) (()(())()) (()()(())) ((()())()) ((())(())) (((()))()) (()(()())) (()((()))) ((()()())) (((())())) ((()(()))) (((()()))) ((((()))))</lang>
Explanation: we are using the parent index representation of a tree. The tree is represented as a sequence of indices of the parent nodes. And we use _ to represent the root node (so our root node has no parent).
incr finds adds each possible child to each node of each tree and forms the result into a simple list of trees.
disp represents a single tree structure in the parenthesized form required by this task.
And for the task example, we want four levels of children from the root, and we want to eliminate redundant representations.
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
- 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:
([{([])}])
([{()()}])
([{()}{}])
([{}{}{}])
([{()}][])
([{}{}][])
([{}][{}])
([{}][][])
([][][][])
Another method by incrementing subtrees: <lang python>treeid = {(): 0}
Successor of a tree. The predecessor p of a tree t is:
1. if the smallest subtree of t is a single node, then p is t minus that node 2. otherwise, p is t with its smalles subtree "m" replaced by m's predecessor
Here "smaller" means the tree is generated earlier, as recorded by treeid. Obviously, predecessor to a tree is unique. Since every degree n tree has a unique degree (n-1) predecessor, inverting the process leads to the successors to tree t:
1. append a single node tree to t's root, or 2. replace t's smallest subtree by its successors
We need to keep the trees so generated canonical, so when replacing a subtree, the replacement must not be larger than the next smallest subtree.
Note that trees can be compared by other means, as long as trees with fewer nodes are considered smaller, and trees with the same number of nodes have a fixed order. def succ(x):
yield(((),) + x) if not x: return
if len(x) == 1:
for i in succ(x[0]): yield((i,))
return
head,rest = x[0],tuple(x[1:]) top = treeid[rest[0]]
for i in [i for i in succ(head) if treeid[i] <= top]:
yield((i,) + rest)
def trees(n):
if n == 1:
yield()
return
global treeid
for x in trees(n-1):
for a in succ(x):
if not a in treeid: treeid[a] = len(treeid)
yield(a)
def tostr(x): return "(" + "".join(map(tostr, x)) + ")"
for x in trees(5): print(tostr(x))</lang>
zkl
Uhhh, isn't "( () (()) () )" the same as "( (()) () () )" (8th sequence)?
<lang zkl>fcn bags(n){
if(not n) return(T(T(0,"")));
[n-1 .. 1, -1].pump(List,bags).flatten() :
bagchain(T(0,""), n-1, _).apply(fcn([(c,s)]){ T(c+1,String("(",s,")")) })
} fcn bagchain(x,n,bb,start=0){
if(not n) return(T(x));
out := List();
foreach i in ([start..bb.len()-1]){
c,s := bb[i];
if(c<=n) out.extend(bagchain(L(x[0]+c, x[1]+s), n-c, bb, i));
}
out
}
- Maybe this lessens eye strain. Maybe not.
fcn replace_brackets(s){
depth,out := 0,Sink(String);
foreach c in (s){
if(c=="("){
out.write("([{"[depth%3]); depth += 1;
}else{
depth -= 1; out.write(")]}"[depth%3]);
} } out.close()
} foreach x in (bags(5)){ println(replace_brackets(x[1])) } println("or"); b:=bags(5); b.apply("get",1).println(b.len());</lang>
- Output:
([{([])}])
([{()()}])
([{()}{}])
([{}{}{}])
([{()}][])
([{}{}][])
([{}][{}])
([{}][][])
([][][][])
or
L("((((()))))","(((()())))","(((())()))","((()()()))","(((()))())","((()())())","((())(()))","((())()())","(()()()())")9