[MINOR SPOILER] Re: Perl Quiz of the Week #23

Daniel Martin <martin-+m399P62/[email protected]> writes:

> Note that one way to check the output of one's program (beyond the
> fact that it should produce distinct lines of only parentheses and
> that those should be balanced, etc.) is given by "Catalan numbers"
> (http://mathworld.wolfram.com/CatalanNumber.html).
>
> Correct programs output C_n lines when given the number n;
> specifically, there should be 1 line output when given "1", 2 lines
> when given "2", 5 lines when given "3", etc.

So I'm sitting here waiting for that 60 hour time limit to expire (if
MJD would post earlier in the morning...), and frustrated that I can't
seem to get my fast solution any closer than 1/64th the speed of Rod
Adams's (1 minute for n=15), and I decide to see if this problem or
one like it is covered in Knuth.

Alas, it isn't, at least not that I can tell.  However, he does, in
section 2.3.4.4, show that there are C_n distinct binary trees (though
Knuth doesn't mention the term "Catalan number" until the bibliography
in 2.3.4.6)

Aha! I thought.  Perhaps I can find a natural correspondence between
binary trees and strings of matching parentheses, and then use the
algorithm for iterating through all possible binary trees.

There is only one problem with that: Knuth doesn't give an efficient
iteration over binary trees, since his goal is just enumeration - he
gives a recursive formula that leads naturally to my initial elegant
but slow solution.  So maybe there's another way to either get a
correspondence between trees or there's a better way of iterating
through the trees.

So does anyone know of a fast way to iterate through all possible
trees of n internal nodes?

Incidentally, my correspondence between binary trees and parenthesis
strings is this, in pseudo-Haskell notation:

string_for :: Tree a -> String

string_for (Leaf _) = ""
string_for (Branch l r) = "(" ++ string_for(l) ++ ")" ++ string_for(r)

As I'm just learning Haskell myself, that may not be right.  In
English:

The string for a leaf is "".
The string for P, where P is not a leaf, is "(A)B", where A is the
string for the left child of P and B is the string for the right.

This probably gives away my first implementation, but the 60 hours are
now up.