#!/usr/bin/perl -w

use strict;

main( @ARGV );
exit( 0 );

# Return the possible starting points for a new open paren:
sub Starts {
    my( $str )= @_;
    my @start;
    my $start= 1 + rindex( $str, "(" );
    pos($str)= $start;
    while( $str =~ /[^()]/g ) {
        push @start, pos($str)-1;
    }
    return @start;
}

# Return the possible ending points:
sub Ends {
    my( $str, $start )= @_;
    pos($str)= $start;
    $str =~ /[^()]+/g;
    return $start+1 .. pos($str);
}

# Iterator that adds one new pair of parens:
sub AddParenIter {
    my( $str )= @_;
    my @start= Starts( $str );
    my @end= Ends( $str, $start[0] );
    return sub {
        if(  ! @end  ) {
            shift @start;
            return   if  ! @start;
            @end= Ends( $str, $start[0] );
        }
        my $new= $str;
        substr( $new, shift(@end), 0 )= ")";
        substr( $new, $start[0], 0 )= "(";
        return $new;
    };
}

# Iterator that adds N new pairs of parens:
sub AddParensIter {
    my( $count, $str )= @_;
    my @iter= AddParenIter( $str );
    return sub {
        my $next;
        while(  not $next= $iter[-1]->()  ) {
            pop @iter;
            return   if  ! @iter;
        }
        while(  @iter < $count  ) {
            push @iter, AddParenIter( $next );
            $next= $iter[-1]->();
        }
        return $next;
    }
}

sub main {
    die "Usage: $0 count string\n",
        "   or: $0 M..N  J..K\n"   unless  2 == @_;
    my( $count, $str )= @_;
    if(  $count !~ /\.\./  ) {
        my $iter= AddParensIter( $count, $str );
        $count= 0;
        while(  $str= $iter->()  ) {
            print ++$count, ": $str\n";
        }
        return;
    }
    my( $m, $n )= split /\.\./, $count;
    my( $j, $k )= split /\.\./, $str;
    print "parens\tlengths\n";
    for my $len (  $j .. $k  ) {
        printf "\t%7d", $len;
    }
    for my $parens (  $m .. $n  ) {
        printf "\n%5d:", $parens;
        for my $len (  $j .. $k  ) {
            my $iter= AddParensIter( $parens, "x"x$len );
            my $count= 0;
            ++$count   while  $iter->();
            printf "\t%7d", $count;
        }
    }
    print "\n";
}

##</code><code>##

> parenperms 3 12
1: (((1)))2
2: ((1))(2)
3: (1)((2))
4: (((1))2)
5: ((1)(2))
6: (((1)2))
7: (((12)))
8: ((1(2)))
9: (1((2)))
10: 1(((2)))

##</code><code>##

> parenperms 1..7 1..7
parens  lengths
              1       2       3       4       5       6       7
    1:        1       3       6      10      15      21      28
    2:        1       6      20      50     105     196     336
    3:        1      10      50     175     490    1176    2520
    4:        1      15     105     490    1764    5292   13860
    5:        1      21     196    1176    5292   19404   60984
    6:        1      28     336    2520   13860   60984  226512
    7:        1      36     540    4950   32670  169884  736164