85 lines
1.4 KiB
Lua
85 lines
1.4 KiB
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)
|