Skip to content

Instantly share code, notes, and snippets.

@randrews
Created May 18, 2011 03:24
Show Gist options
  • Save randrews/977940 to your computer and use it in GitHub Desktop.
Save randrews/977940 to your computer and use it in GitHub Desktop.
Enumerate all trees
-- Copyright (C) 2011 Ross Andrews
--
-- This program is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program. If not, see <http://www.gnu.org/licenses/>.
function tree_str(tree)
if #tree == 0 then return ""
else
local subtrees = {}
for _, subtree in ipairs(tree) do
table.insert(subtrees, "(" .. tree_str(subtree) .. ")")
end
return table.concat(subtrees, " ")
end
end
function bits(n)
local b = {}
while n > 0 do
b[#b+1] = n%2
n = (n - n%2) / 2
end
return b
end
function make_tree(node_count, n)
local b = bits(n)
local nodes = { {} }
local current_node = nodes
while node_count > 1 do
node_count = node_count - 1
if b[node_count] == 1 then
current_node = current_node[#current_node]
end
current_node[#current_node + 1] = {}
end
return nodes
end
for n = 0,7 do
local str = tree_str(make_tree(4, n))
print(str)
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment