79 lines
1.3 KiB
Ruby
79 lines
1.3 KiB
Ruby
TREE_LIST = []
|
|
OFFSET = []
|
|
|
|
for i in 0..31
|
|
if i == 1 then
|
|
OFFSET << 1
|
|
else
|
|
OFFSET << 0
|
|
end
|
|
end
|
|
|
|
def append(t)
|
|
TREE_LIST << (1 | (t << 1))
|
|
end
|
|
|
|
def show(t, l)
|
|
while l > 0
|
|
l = l - 1
|
|
if t % 2 == 1 then
|
|
print '('
|
|
else
|
|
print ')'
|
|
end
|
|
t = t >> 1
|
|
end
|
|
end
|
|
|
|
def listTrees(n)
|
|
for i in OFFSET[n] .. OFFSET[n + 1] - 1
|
|
show(TREE_LIST[i], n * 2)
|
|
print "\n"
|
|
end
|
|
end
|
|
|
|
def assemble(n, t, sl, pos, rem)
|
|
if rem == 0 then
|
|
append(t)
|
|
return
|
|
end
|
|
|
|
if sl > rem then
|
|
sl = rem
|
|
pos = OFFSET[sl]
|
|
elsif pos >= OFFSET[sl + 1] then
|
|
sl = sl - 1
|
|
if sl == 0 then
|
|
return
|
|
end
|
|
pos = OFFSET[sl]
|
|
end
|
|
|
|
assemble(n, t << (2 * sl) | TREE_LIST[pos], sl, pos, rem - sl)
|
|
assemble(n, t, sl, pos + 1, rem)
|
|
end
|
|
|
|
def makeTrees(n)
|
|
if OFFSET[n + 1] != 0 then
|
|
return
|
|
end
|
|
if n > 0 then
|
|
makeTrees(n - 1)
|
|
end
|
|
assemble(n, 0, n - 1, OFFSET[n - 1], n - 1)
|
|
OFFSET[n + 1] = TREE_LIST.length()
|
|
end
|
|
|
|
def test(n)
|
|
if n < 1 || n > 12 then
|
|
raise ArgumentError.new("Argument must be between 1 and 12")
|
|
end
|
|
|
|
append(0)
|
|
|
|
makeTrees(n)
|
|
print "Number of %d-trees: %d\n" % [n, OFFSET[n + 1] - OFFSET[n]]
|
|
listTrees(n)
|
|
end
|
|
|
|
test(5)
|