Well, I was just about to finish previewing my idea when I realized that it didn't find arrangements of parens like (()()). Which lead me to a simpler solution anyway.

In any case, the trick is to come up with a order for the solutions so that you can find the solutions in that order and then you don't have to worry about checking for duplicates.

This is important because finding duplicates requires you be able to compare a new result to all previous results but the number of results for this type of problem quickly becomes so huge that such a comparison becomes infeasible.

For this problem, I think we need to order first either based on the position of the open parens, or based on the position of the closed parens. So, for a final arrangement like (1((2)3))(4), we can build up the parens either like (123)4 -> (1(23))4 -> (1((2)3)4 -> (1((2)3))(4) or like 1(2)34 -> 1((2)3)4 -> (1((2)3))4 -> (1((2)3))(4). Let's go with the first case.

So, start by building a loop or iterator (we won't have enough memory if we start computing whole lists of solutions along the way) that adds one set of parens: (1)234, (12)34, (123)4, (1234), 1(2)34, 1(23)4, 1(234), 12(3)4, 12(34), and 123(4).

Then improve this so that it knows to add the next set of parens such that 1) nesting is not violated and 2) the opening paren is inserted *after* all of the existing opening parens. Then apply this solution N times to get N sets of parens.

So, if you have 1(23)4, adding the next set of parens would proceed like so: 1((2)3)4, 1((23))4, 1(2(3))4, 1(23)(4). That is, start with the opening paren in the first possible location (right after the last opening paren already present) and progress this position forward one step at a time. For each position of the opening paren, step the position of the closing paren along, starting right after the digit after the new open paren, and continuing until the end of the continguous string of digits (after which we'd either hit end of string or violate nesting of parens).

This very last part almost screams "regex", and with experimental features you could even get the regex engine to find all of these for you as it back-tracks matching \d+? over and over. But such wouldn't give us an iterator (and I don't like using experimental features), so...

#!/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";
}
[download]

Which can give you all of the results:

> 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)))
[download]

> 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
[download]