List rooted trees: Difference between revisions
→{{header|Perl}}
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 1,047:
(()()()())
</pre>
=={{header|Lua}}==
{{trans|Java}}
<lang lua>tree_list = {}
offset = {}
function init()
for i=1,32 do
if i == 2 then
table.insert(offset, 1)
else
table.insert(offset, 0)
end
end
end
function append(t)
local v = 1 | (t << 1)
table.insert(tree_list, v)
end
function show(t, l)
while l > 0 do
l = l - 1
if (t % 2) == 1 then
io.write('(')
else
io.write(')')
end
t = t >> 1
end
end
function listTrees(n)
local i = offset[n]
while i < offset[n + 1] do
show(tree_list[i + 1], n * 2)
print()
i = i + 1
end
end
function assemble(m, t, sl, pos, rem)
if rem == 0 then
append(t)
return
end
local pp = pos
local ss = sl
if sl > rem then
ss = rem
pp = offset[ss]
elseif pp >= offset[ss + 1] then
ss = ss - 1
if ss == 0 then
return
end
pp = offset[ss]
end
assemble(n, t << (2 * ss) | tree_list[pp + 1], ss, pp, rem - ss)
assemble(n, t, ss, pp + 1, rem)
end
function 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
end
function test(n)
append(0)
makeTrees(n)
print(string.format("Number of %d-trees: %d", n, offset[n+1] - offset[n]))
listTrees(n)
end
init()
test(5)</lang>
{{out}}
<pre>Number of 5-trees: 9
((((()))))
(((()())))
((()(())))
((()()()))
(()((())))
(()(()()))
((())(()))
(()()(()))
(()()()())</pre>
=={{header|Perl}}==
| |||