I saw this on sci.math, and thought "one liner" ;-)
I even think a DP non-recursive approach should be quite quick.
Keeping the output in the logical order might cost a few strokes.
#!/usr/bin/perl
$count = $ARGV[0];
print join "\n", pren($count), "";
sub pren
{
my @list = ();
(my $n) = @_;
if ($n == 0) {push(@list, "")}
elsif($n == 1) {push(@list, "()")}
elsif($n > 1)
{
foreach $k (0 .. $n-1)
{
foreach $p1 (pren($k))
{
foreach $p2 (pren($n - 1 - $k))
{
push @list, sprintf "(%s)%s", $p1, $p2;
}
}
}
}
return @list;
}
________________________
$ ./parens.pl 5 | cat -n
1 ()()()()()
2 ()()()(())
3 ()()(())()
4 ()()(()())
5 ()()((()))
6 ()(())()()
7 ()(())(())
8 ()(()())()
9 ()((()))()
10 ()(()()())
11 ()(()(()))
12 ()((())())
13 ()((()()))
14 ()(((())))
15 (())()()()
16 (())()(())
17 (())(())()
18 (())(()())
19 (())((()))
20 (()())()()
21 (()())(())
22 ((()))()()
23 ((()))(())
24 (()()())()
25 (()(()))()
26 ((())())()
27 ((()()))()
28 (((())))()
29 (()()()())
30 (()()(()))
31 (()(())())
32 (()(()()))
33 (()((())))
34 ((())()())
35 ((())(()))
36 ((()())())
37 (((()))())
38 ((()()()))
39 ((()(())))
40 (((())()))
41 (((()())))
42 ((((()))))
() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed
[stolen with permission from Daniel B. Cristofani]
____________________________________________________________________________________
Never miss a thing. Make Yahoo your home page.
http://www.yahoo.com/r/hs
