Re: [SPOILER] Solution for Quiz of the Week #23 : parens

Here's my fast, but hard to read, version:

#!/usr/bin/perl
use strict;

my $n = shift;
die "Usage: $0 n [where n is a positive integer]" unless defined $n
and $n !~ /\D/;
exit unless $n;
print "()\n" and exit if $n == 1;

my (@parens, @right, @left);
@right = (')') x (2*$n-2);
@left = ('(') x (2*$n-2);
my $limit = 3; 
my @code = ('for my $v1 (0..1) {');
for (2..$n-1) {
    push @code, "for my \$v$_ (\$v" . ($_-1) . "+1..$limit) {";
    $limit += 2;
}
push @code, '@parens = @right; @parens[', (join ',', map "\$v$_", (1..$n-1)), 
    '] = @left; print join "", "(", @parens, ")\n"', '}' x ($n-1);
eval join '', @code;

Here's another with the same basic algorithm, but using
Algorithm::Loops to build the loops, instead of self-generated
code. It's slower, but pretty much as hard to read.

#!/usr/bin/perl
use strict;
use warnings;
use Algorithm::Loops qw( NestedLoops );

my $n = shift;
die "Usage: $0 n [where n is a positive integer]" unless defined $n
and $n !~ /\D/;
exit unless $n;
print "()\n" and exit if $n == 1;

sub create_iterator_closure {
   my $p = $_[0]*2-1;
   return sub { [ $_+1..$p ] };
}

my (@parens, @right, @left);
@right = (')') x (2*$n-2);
@left = ('(') x (2*$n-2);

my $loop = [[0..1]];
push(@$loop, create_iterator_closure($_)) for (2..$n-1);
my $iter = NestedLoops($loop);
while (my @list = $iter->()) {
    @parens = @right;
    @parens[@list] = @left;
    print join '', '(', @parens, ')', "\n";
}

I solicited and received help getting the NestedLoops
parameter right at Perlmonks (thanks to ikegami, who supplied
the create_iterator_closure routine as it appears here.) I considered
trying to change the values in my question so it wouldn't act as a
spoiler for any qotw participants reading Perlmonks. I decided the
relationship between my question and the quiz was obscure enough
already.

http://www.perlmonks.org/index.pl?node_id=387799

I spent some of this afternoon at the UC Berkeley Math Library looking
at combinatorics textbooks trying to see if the matherati offered some
clever solution to this. I didn't find one. All those combinatorial
mathematicians want to do is to _avoid_ enumerating sequences by
coming up with clever ways to generate their counts. (It is pretty
astonishing how many problems this is equivalent to, though.)

There's a really interesting pattern lurking in the relationship
between these strings evaluated as binary numbers, but I haven't quite
cracked it. I really hope someone else's solution depends on it.