Enumerate all trees

all_trees.lua

--    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