Re: Perl Quiz of the Week #23

Mark Jason Dominus wrote:

> Write a program, 'parens',which gets a command line argument, n',
> which is an integer.  The program should print all the
> properly-balanced strings of parentheses of length 2n.

So I worked a bit, and pretty quickly got an algorithm straight.
However, it's fairly obvious that my algorithm is exponential.
Obviously, the number of results is also exponential, but I was hoping
that I could

For 'n' up to 10, the time is under a second.  However, on a very nice
machine, I very quickly go bad.  My runtimes seem to be

                4**N * 8e-7 seconds.

When N = 10, this is 0.8 seconds.  When N = 14, this is over three
minutes.  I've been waiting nine minutes for N = 15, and don't expect
an answer for another three minutes (at least).  It will be a really
long wait for N = 16.

I'm wondering if there is a less expensive exponential solution --
maybe a non-recursive one.  For example, the Towers of Hanoi, which
seems recursive, has a very simple non-recursive (looping) solution.

Of course, what I'd really like is to have a (non-exponential)
algorithm that calculates the number of lines in the answer.  So far,
I have the following results.

 N     Lines
 -     -----
 0         0 
 1         1 
 2         2 
 3         5 
 4        14 
 5        42 
 6       132 
 7       429 
 8      1430
 9      4862
10     16796
11     58786
12    208012
13    742900 
14   2674440
15   9694845 

I'm not waiting for N=16.

-- 
Colin