List rooted trees: Difference between revisions
→{{header|Sidef}}
Line 1,645:
(((())))
</pre>
=={{header|Ruby}}==
{{trans|Java}}
<lang 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)</lang>
{{out}}
<pre>Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())</pre>
=={{header|Sidef}}==
| |||