Re: Perl Quiz of the Week #23

On Wed, Sep 01, 2004 at 12:50:14PM -0400, Mark Jason Dominus wrote:
> and for argument '4', the output should be:
> 
>         (((())))
>         ((()()))
>         ((())())
>         ((()))()
>         (()(()))
>         (()()())
>         (()())()
>         (())(())
>         (())()()
>         ()((()))
>         ()(()())
>         ()(())()
>         ()()(())
>         ()()()()
> 
> in some order.

That's a very strange sample order; I have a hard time picturing an
algorithm coming up with it.  I'd expect "((()))()" to come after
"(()()())".

It's going to be a long 60 hours; I've got a simple recursive solution
(that I haven't had the patience to see if it will finish 15 pairs), a
somewhat faster iterative by generation solution (that runs out of
memory for 16 pairs), and am working on a memory-friendly subroutine
that looks up the Nth string of a given width, that I'm hoping to
transmogrify into a memory-friendly but fast-enough full solution.