Re: [SPOILER] Solution for Quiz of the Week #23 : parens

Zed Lopez <[email protected]>:
> I spent some of this afternoon at the UC Berkeley Math Library looking
> at combinatorics textbooks trying to see if the matherati offered some
> clever solution to this. I didn't find one. All those combinatorial
> mathematicians want to do is to _avoid_ enumerating sequences by
> coming up with clever ways to generate their counts. 

You were looking in the wrong department.  Mathematicians look for
ways to count stuff without enumerating them.  Computer scientists
enumerate.  I posed this problem because last week I was reading
section 7.1.2.6 of _The Art of Computer Programming_, which treats
this problem in the usual Knuthianly exhaustive detail.

> (It is pretty
> astonishing how many problems this is equivalent to, though.)

In fact, the Knuth section 7.2.1.6 is titled "Generating All Trees",
because there's a simple corespondence between the parenthesis strings
and trees.  In general, "(AB..Z)" corresponds to

        *
       /|...\
      A B ...Z

so, for example, (()()(()))() corresponds to the tree

        *
       / \
      *   *
     /|\
    * * *
        |
        *

And then there's a well-known correspondence between these general
trees and binary trees.  So if you can enumate the parenthes, you can
enumate all the trees with n nodes, and all the binary trees with n nodes.


> There's a really interesting pattern lurking in the relationship
> between these strings evaluated as binary numbers, but I haven't quite
> cracked it. I really hope someone else's solution depends on it.

Mine does, sort of, although I realized after a day or so that I could
make the program faster by getting rid of the numbers and operating
directly on the strings.

I'll post my "wow, look at that" solution first, and then try to
explain how I came up with it.