Just chipping in...
Phil Carmody
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
Jasper
> 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.
First pass:
sub f {
my($i,$c,@p)=@_;
$i?
map{f($i-1,$c+/\(/-/\)/,@p,$_)}!$c?'(':$c-$i?qw{) (}:')':
print join'',@p
}
f($ARGV[0]*2);
I suppose that will give an undef for 0...
--
Jasper
Jasper
> On 15/11/2007, Phil Carmody <thefa...@yahoo.co.uk> wrote:
> > 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.
>
and (mostly) with a regex :):wq
\$h{$_='()'x$ARGV[0]};
while(/\)\(/){
s/\)(.*?)\(/$1()/;
\$h{$_,reverse};
}
print for sort keys %h;
--
Jasper
Jasper
Should read:
\$h{$_='()'x$ARGV[0]};
\$h{$_,reverse}while s/\)(.*?)\(/$1()/;
print for sort keys %h;
of course!
--
Jasper
Jasvir Nagra
rather long one!)
#!/usr/bin/perl -l
$n=pop;$"=$/;print"@{[w($n)]}";sub
w{my($n)=pop;!$n?@_="":$n==1?@_="()":a;if($n>1){for$k(0..--$n){for$p(w($k)){push@_,"($p)$_"for
w($n-$k)}}}@_}
-- jas
--
Jasvir Nagra
http://www.cs.auckland.ac.nz/~jas
Jasper
Phil points out that reverse isn't actually a mirror (and scalar
reverse makes this horribly incorrect), so it turns out I have to do
this in two passes.
\$h{$_='()'x $ARGV[0]};
\$h{$_}while s/\)(.*?)\(/$1()/;
$_='()'x pop;
\$h{$_}while s/(.*)\)(.*?)\(/$1()$2/;
print for sort keys %h;
Hopefully someone can fix that :D
--
Jasper
Jasper
either. It looks like it does without counting the results, though :S
--
Jasper
Tuomo Salo
- From the keyboard of Phil Carmody (2007-11-15 15:05):
> I saw this on sci.math, and thought "one liner" ;-)
While I could not squeeze this down to a one 80 char line, there is only
one line that does not begin with a # :-)
#!perl -l
$\=~s#(.*)\n#"$1(\n"x($1=~y/(//<$a)."$1)\n"x($1=~y/)//*2<$_-1)
#gefor 1..2*($a=pop);print
I tried to do the generation by hand, implemented that method as a
regex, and polished (or should I say disfigured) the result with a
couple of standard golfing tricks. Notice the lack of escaped parens,
btw :-)
There are probably a couple of mrmagoos there, at least you could lose
a couple of chars (along with any perceived one-linerness) by replacing
the "\n":s with literal newlines.
Cheers,
-bass
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iQB1AwUBR0GxVPbPZUB64qcJAQFFFAL/ejNBEfzY9+PwNSS+EtakB+UC7RpfzBu5
FmVwYQ8JXoEiCPjuSfqEA+D6I5qhioNhQsuMOoG3YEbaWbhjRuEpTcNmdIhbDBi1
g8sRXE1rOlCO+wgR4ZVUjXoROrhj4AoN
=4jPH
-----END PGP SIGNATURE-----
Phil Carmody
> -----BEGIN PGP SIGNED MESSAGE-----
> - From the keyboard of Phil Carmody (2007-11-15 15:05):
> > I saw this on sci.math, and thought "one liner" ;-)
>
> While I could not squeeze this down to a one 80 char line, there is only
> one line that does not begin with a # :-)
>
> #!perl -l
> $\=~s#(.*)\n#"$1(\n"x($1=~y/(//<$a)."$1)\n"x($1=~y/)//*2<$_-1)#gefor
1..2*($a=pop);print
>
> I tried to do the generation by hand, implemented that method as a
> regex, and polished (or should I say disfigured) the result with a
> couple of standard golfing tricks. Notice the lack of escaped parens,
> btw :-)
>
> There are probably a couple of mrmagoos there, at least you could lose
> a couple of chars (along with any perceived one-linerness) by replacing
> the "\n":s with literal newlines.
Masterful! Hyvä Tuomo! I can only begin to work out how it works!
Phil
Juho Snellman
> From the keyboard of Phil Carmody (2007-11-15 15:05):
> > I saw this on sci.math, and thought "one liner" ;-)
>
> While I could not squeeze this down to a one 80 char line, there is only
> one line that does not begin with a # :-)
>
> #!perl -l
> $\=~s#(.*)\n#"$1(\n"x($1=~y/(//<$a)."$1)\n"x($1=~y/)//*2<$_-1)
> #gefor 1..2*($a=pop);print
The following is technically speaking not a one-liner, but is 80 characters
total split to multiple lines:
#!perl
$_||=11x
pop;/1(1*)
?(1?)/?map$_&&do$0,$1!=$'&&"$`($1
1$2$'","$`)$1
$'"x$2:print
--
Juho Snellman
Tuomo Salo
- From the keyboard of Tuomo Salo (2007-11-19 17:52):
> From the keyboard of Phil Carmody (2007-11-15 15:05):
>> I saw this on sci.math, and thought "one liner" ;-)
>
> While I could not squeeze this down to a one 80 char line,
Scratch that!
Trading (any) performance and utility (whatsoever) for brevity, here's
finally a one liner version:
#!perl -l
$r=qr/4(??{$r})*2/;s/^$r*$/y*42*()**print/efor($=x=pop)/2..$=
Not only accomplishing the given task, this little script will also use
up all your CPU and more! Use argument 4 for extra sluggishness!
Argument >= 4 will even overflow the counter variable to protect your
precious processor cycles!
-bass
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iQB1AwUBR0MRZ/bPZUB64qcJAQH6oAL/dTSy5U6q0+XCdRizhPC9QV381Lpwja+X
0fZn3IUP9q7ez85RF0j4CP4DSUVbZGNVGnqqNICbNQZo+I2IswG1ZULLtHqiRMkm
E5Mq4U7wULsYqVcUPmGvsnz+B8AWA6OG
=lT/i
-----END PGP SIGNATURE-----
Tuomo Salo
#!perl -l
$r=qr/\((??{$r})*\)/;map/^$r+$/&&print,glob"{(,)}"x2x pop
-bass
Jasper
Just thought of this.
Probably has performance issues and is a little bit longer. Boo!
#!perl -l
$l=2*pop;fork?$l>$c++?$_.='(':exit:$c--?$_.=')':exit while$l--;print
Doesn't order correctly (it would if I added a wait), doesn't print
right, but everyone loves potentially killing their machine with a
fork. Can't get rid of the two exits, so there seems to be flab for
sure
--
Jasper
Daniel Tiefnig
> This one has no performance issues and is even a little bit shorter.
> Yay!
AND it does print lines in wrong order! :o)
Doesn't it? It does for me.
lg,
daniel
Jasper
> Just thought of this.
>
> Probably has performance issues and is a little bit longer. Boo!
>
> #!perl -l
> $l=2*pop;fork?$l>$c++?$_.='(':exit:$c--?$_.=')':exit while$l--;print
>
> Doesn't order correctly (it would if I added a wait), doesn't print
> right, but everyone loves potentially killing their machine with a
> fork. Can't get rid of the two exits, so there seems to be flab for
> sure
Flabby indeed
#!perl -l
$_.=fork?$c--?')':exit:++$c&&'('for($_)x(2*pop);$c||print
That's the same length as bass, but still with the same problems. A
waitpid does solve the ordering problem, but the only way to stop the
overall parent exiting before all the permutations have printed is to
do something awful. Those solutions add lotsa characters... :(
--
Jasper
Jasper
week, so I spent another 10 minutes looking at it.
#!perl -l
eval'$c-=fork?$c?s//(/:exit:- s//)/;'x2x pop or print
is the shortest I can get with this forking method, which still prints
the results in a random order, but it's shorter than bass's.
Jasper
--
Jasper
Jasper
2008/5/19 Jasper <jasper...@gmail.com>:
> 2007/11/20 Tuomo Salo <ba...@iki.fi>:
>> This one has no performance issues and is even a little bit shorter. Yay!
>>
>> #!perl -l
>> $r=qr/\((??{$r})*\)/;map/^$r+$/&&print,glob"{(,)}"x2x pop
>
> OK, so it took me a number(!) of months, but this is shorter, and
> prints in order..
>
> #!perl -l
> eval'$c-=fork?wait&&$c?s//(/:.1:- s//)/;'x2x pop||print
>
> Didn't I read a proverb somewhere about a tortoise and a hare, and the
> tortoise losing his job, and the hare shifting the blame onto the
> ex-tortoise?
> --
> Jasper
>
--
Jasper