{"id":18,"date":"2011-05-17T22:24:26","date_gmt":"2011-05-18T03:24:26","guid":{"rendered":"http:\/\/www.playwithlua.com\/?p=18"},"modified":"2020-05-22T13:20:46","modified_gmt":"2020-05-22T18:20:46","slug":"enumerating-all-trees","status":"publish","type":"post","link":"http:\/\/www.playwithlua.com\/?p=18","title":{"rendered":"Enumerating All Trees"},"content":{"rendered":"

This is a problem in The Art of Computer Programming<\/em> volume 4A, which only came out a few months ago. My solution isn’t Knuth’s solution, mostly because I don’t understand<\/em> Knuth’s solution, but it works and it’s fairly easy to explain.<\/p>\n

The problem is this: given a number of nodes (like, say, 4), generate every possible arrangement of those nodes into a tree. So this is one:<\/p>\n\n

(<\/span>)<\/span> (<\/span>)<\/span> (<\/span>)<\/span> (<\/span>)<\/span><\/pre><\/div><\/div><\/div>\n\n

\nThis is another one:<\/p>\n\n
(<\/span>)<\/span> (<\/span>)<\/span> (<\/span>(<\/span>)<\/span>)<\/span><\/pre><\/div><\/div><\/div>\n\n

\nAnd so on. For n nodes there are 2n-1<\/sup> possible trees. And it’s not immediately obvious how to generate them.
\n
\nKnuth’s solution builds the strings directly, through some magic I don’t quite understand. I think<\/em> he’s doing the same general thing I am, but he’s got a way to do it directly, whereas I’m going to build the trees in memory first, out of Lua tables, and then print strings from them.<\/p>\n
So, first I want a simple way to print the strings. This function takes a table and returns the parentheses that represent it:<\/p>\n\n
function<\/span> tree_str(<\/span>tree)<\/span>\n   if<\/span> #<\/span>tree ==<\/span> 0<\/span> then<\/span> return<\/span> ""<\/span>\n   else<\/span>\n\t  local<\/span> subtrees =<\/span> {<\/span>}<\/span>\n \n\t  for<\/span> _,<\/span> subtree in<\/span> ipairs<\/span>(<\/span>tree)<\/span> do<\/span>\n\t\t table.insert<\/span>(<\/span>subtrees,<\/span> "("<\/span> ..<\/span> tree_str(<\/span>subtree)<\/span> ..<\/span> ")"<\/span>)<\/span>\n\t  end<\/span>\n \n\t  return<\/span> table.concat<\/span>(<\/span>subtrees,<\/span> " "<\/span>)<\/span>\n   end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
We can test it like this:<\/p>\n\n
tree_str(<\/span>{<\/span> {<\/span>}<\/span>,<\/span> {<\/span>}<\/span>,<\/span> {<\/span>{<\/span>}<\/span>,<\/span> {<\/span>}<\/span>}<\/span>}<\/span>)<\/span> --&gt; "() () (() ())"<\/span><\/pre><\/div><\/div><\/div>\n\n
Simple enough. Now that that’s out of the way, how do we actually do this? Well, let’s first try to figure it out inductively. If we have the set of trees for n-1 nodes, and we add an nth node, we can figure it will double the number of trees: each tree of n-1 can either be a descendent of the new node or a sibling of it.<\/p>\n
Since there is only one tree for the first node, and each one doubles the count, there are\u00a02n-1<\/sup> trees. If we can figure out some 1-to-1 correlation between bit fields and trees, we can just count from 1 to 2n-1<\/sup>-1 and generate the tree for each one. So, how to do that?<\/p>\n
The way I figured out is, each node’s bit determines whether it’s a sibling or a child of the previous node. We keep a current_node<\/code> reference, and if the bit is zero, we push a new table into it; if it’s 1, we find current_node<\/code>‘s last child, make that the new current_node<\/code>, and then add a child to that.<\/p>\n
Right away we run into a problem, because Lua doesn’t have any bitwise operators. So let’s make a quick function to dump out all the bits in a number:<\/p>\n\n
function<\/span> bits(<\/span>n)<\/span>\n   local<\/span> b =<\/span> {<\/span>}<\/span>\n   while<\/span> n &gt;<\/span> 0<\/span> do<\/span>\n\t  b[<\/span>#<\/span>b+<\/span>1<\/span>]<\/span> =<\/span> n%<\/span>2<\/span>\n\t  n =<\/span> (<\/span>n -<\/span> n%<\/span>2<\/span>)<\/span> \/<\/span> 2<\/span>\n   end<\/span>\n   return<\/span> b\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
We don’t care what the indices are, so we may as well have them be 1-indexed so that we can use ipairs<\/code>. We can use this function to generate all the trees, like this:<\/p>\n\n
function<\/span> make_tree(<\/span>node_count,<\/span> n)<\/span>\n   local<\/span> b =<\/span> bits(<\/span>n)<\/span>\n   local<\/span> nodes =<\/span> {<\/span> {<\/span>}<\/span> }<\/span>\n   local<\/span> current_node =<\/span> nodes\n \n   while<\/span> node_count &gt;<\/span> 1<\/span> do<\/span>\n\t  node_count =<\/span> node_count -<\/span> 1<\/span>\n\t  if<\/span> b[<\/span>node_count]<\/span> ==<\/span> 1<\/span> then<\/span>\n\t\t current_node =<\/span> current_node[<\/span>#<\/span>current_node]<\/span>\n\t  end<\/span>\n\t  current_node[<\/span>#<\/span>current_node +<\/span> 1<\/span>]<\/span> =<\/span> {<\/span>}<\/span>\n   end<\/span>\n \n   return<\/span> nodes\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
The loop is structured a little weirdly because we want to skip the first node; it can’t possibly be a child of the previous node even if it’s a 1.<\/p>\n
So now, we can generate a single tree, so let’s loop through to make all the trees:<\/p>\n\n
for<\/span> n =<\/span> 0<\/span>,<\/span>7<\/span> do<\/span>\n   local<\/span> str =<\/span> tree_str(<\/span>make_tree(<\/span>4<\/span>,<\/span> n)<\/span>)<\/span>\n   print<\/span>(<\/span>str)<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
And we see:<\/p>\n\n
(<\/span>)<\/span> (<\/span>)<\/span> (<\/span>)<\/span> (<\/span>)<\/span>\n(<\/span>)<\/span> (<\/span>)<\/span> (<\/span>(<\/span>)<\/span>)<\/span>\n(<\/span>)<\/span> (<\/span>(<\/span>)<\/span> (<\/span>)<\/span>)<\/span>\n(<\/span>)<\/span> (<\/span>(<\/span>(<\/span>)<\/span>)<\/span>)<\/span>\n(<\/span>(<\/span>)<\/span> (<\/span>)<\/span> (<\/span>)<\/span>)<\/span>\n(<\/span>(<\/span>)<\/span> (<\/span>(<\/span>)<\/span>)<\/span>)<\/span>\n(<\/span>(<\/span>(<\/span>)<\/span> (<\/span>)<\/span>)<\/span>)<\/span>\n(<\/span>(<\/span>(<\/span>(<\/span>)<\/span>)<\/span>)<\/span>)<\/span><\/pre><\/div><\/div><\/div>\n\n
And there, we’ve enumerated all the possible trees with four nodes! Here’s the code.<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
This is a problem in The Art of Computer Programming volume 4A, which only came out a few months ago. My solution isn’t Knuth’s solution, mostly because I don’t understand Knuth’s solution, but it works and it’s fairly easy to explain. The problem is this: given a number of nodes (like, say, 4), generate every […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts\/18"}],"collection":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=18"}],"version-history":[{"count":0,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts\/18\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=18"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=18"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=18"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}