Re: Perl Quiz of the Week #23

Yitzchak Scott-Thoennes wrote:

>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
>"(()()())".
>
Funny. I have two different algorithms which come up with the above order.

My fastest comes up with them in this order:

(((())))
((()))()
()((()))
((())())
(())()()
(()(()))
()(())()
()()(())
((()()))
(()())()
()(()())
(()()())
()()()()

It does n=18 in 73.78 seconds on a Win2k laden Athlon 950 (with printing 
turned off).
My timings say that it computes in e^0.97n time, as opposed to one of 
the others that takes e^2.7n time....

-- Rod Adams