#!perl
use strict;
use warnings;

sub parens_permute_int {
    my $n=shift;
    return unless $n;
    my $verbose=shift;
    my $N=2*$n;
    my @paren=qw[ ( ) ];
    my $count=0;
    my @results;
    NUM:
    for(my $int=2**$n-1;$int<2**($N-1);$int+=2) {
        my @bit=split //,sprintf "%0*b",$N,$int;
        my $sum=0;
        BIT:
        for my $pos (0..$#bit) {
            my $digit=$bit[$pos];
            $sum+=$digit ? -1 : 1;
            next NUM if $sum<0          # too many close brackets
                     or $sum>@bit-$pos; # too many open brackets
        }
        if ($verbose) {
            push @results,sprintf "%4d(%4d) %s",++$count,$int,
                    join "",map $paren[$_],@bit;
        } else {
            push @results,join '',map($paren[$_],@bit);
        }
    }
    return @results
}

sub parens_permute_rex {
    my $n=shift;
    return unless $n;
    our (@pattern,%seen);
    local @pattern=("()" x $n);
    local %seen=(@pattern,1);
    my $cur=0;
    while ($cur<@pattern) {
        $pattern[$cur++]=~m/^\((.*?)\)(.*)\((.*?)\)$
          (??{my $str="($1($2)$3)";
              push @pattern,$str unless $seen{$str}++; 'a'})/x;
    }
    #print "$_:$seen{$_}\n" for reverse sort keys %seen;
    return @pattern;
}

unless (@ARGV) {
    warn "Testing.\n";
    for my $n (0..4) {
        print "For \$n=$n:\n";
        my @res1=parens_permute_int($n,1);
        my @res2=sort(parens_permute_rex($n));
        my $num=$#res1>=$#res2 ? $#res1 : $#res2;
        foreach my $i (0..$num) {
            print $res1[$i]=~/\Q$res2[$i]\E/ ? '= ' 
                   : '? ',$res1[$i]||'missing',"  # 
",$res2[$i]||'missing',"\n";
        }
        print "----\n";
    }
} else {
    my ($n,$ver)=@ARGV;
    if ($ver and $ver=~/int/) {
      parens_permute_int();
    } else {
      parens_permute_rex();
    }
}

__END__
Testing.
For $n=0:
----
For $n=1:
=    1(   1) ()  #  ()
----
For $n=2:
=    1(   3) (())  #  (())
=    2(   5) ()()  #  ()()
----
For $n=3:
=    1(   7) ((()))  #  ((()))
=    2(  11) (()())  #  (()())
=    3(  13) (())()  #  (())()
=    4(  19) ()(())  #  ()(())
=    5(  21) ()()()  #  ()()()
----
For $n=4:
=    1(  15) (((())))  #  (((())))
=    2(  23) ((()()))  #  ((()()))
=    3(  27) ((())())  #  ((())())
=    4(  29) ((()))()  #  ((()))()
=    5(  39) (()(()))  #  (()(()))
=    6(  43) (()()())  #  (()()())
=    7(  45) (()())()  #  (()())()
=    8(  51) (())(())  #  (())(())
=    9(  53) (())()()  #  (())()()
=   10(  71) ()((()))  #  ()((()))
=   11(  75) ()(()())  #  ()(()())
=   12(  77) ()(())()  #  ()(())()
=   13(  83) ()()(())  #  ()()(())
=   14(  85) ()()()()  #  ()()()()
----




-- 
First they ignore you, then they laugh at you, then they fight you,
then you win.
  +Gandhi

