Write a program, 'parens', which gets a command line argument, 'n',
which is an integer.  The program should print all the
properly-balanced strings of parentheses of length 2n.  For example,
given the argument '3', the program should print these five lines:

        ((()))
        (()())
        (())()
        ()(())
        ()()()

in some order.  (The order is not important.)  

For the argument '1'; the output should be:
        
        ()

and for argument '4', the output should be:

        (((())))
        ((()()))
        ((())())
        ((()))()
        (()(()))
        (()()())
        (()())()
        (())(())
        (())()()
        ()((()))
        ()(()())
        ()(())()
        ()()(())
        ()()()()

in some order.

#!/usr/bin/perl
use strict;
use warnings;

use File::Basename;

=head1 QUEST

    Write a program, 'parens', which gets a command line argument, 'n',
    which is an integer.  The program should print all the
    properly-balanced strings of parentheses of length 2n.  For example,
    given the argument '3', the program should print these five lines:

           ((()))
           (()())
           (())()
           ()(())
           ()()()

    in some order.  (The order is not important.)  

    For the argument '1'; the output should be:
           
           ()

    and for argument '4', the output should be:

           (((())))
           ((()()))
           ((())())
           ((()))()
           (()(()))
           (()()())
           (()())()
           (())(())
           (())()()
           ()((()))
           ()(()())
           ()(())()
           ()()(())
           ()()()()

    in some order.

=cut


main();
exit;


sub next_parenthesis ($$) {
    my ($is, $n) = @_;
    my @np;

    my $open  = () = $is =~ m/\(/g;
    my $close = () = $is =~ m/\)/g;

    push @np, '(' if $open < $n;
    push @np, ')' if $close < $open;

    return @np;
}


sub main {
    my $n = $ARGV[0];

    die "syntax: ", basename($0),
        " N\n\twhere N is a natural number (number of pairs of parenthesis)\n"
        unless defined $n and $n > 0;

    my @output = ('');

    for my $position (1 .. 2*$n) {
        my @output2;

        for my $is (@output) {
            push @output2, "$is$_" for next_parenthesis($is, $n);
        }
        @output = @output2;
    }

    printf "%3d: %s\n", $_+1, $output[$_] for 0.. $#output;
}

#!/usr/bin/perl
$n=$ARGV[0];@o=('');for(1..2*$n){my@q;for(@o){$o=()=m/\(/g;$c=()=m/\)/g;push@q,"$_("if $o<$n;push@q,"$_)"if$c<$o;}@o=@q;}print"$_\n"for@o;

#!perl -l

map/.*(??{$t{"$`($&)$'"}=1})/,@p=@p?keys%t:'',%t=()for 0..shift;print for@p

#!perl -l

map{/\d/||print while s/0(.*?)1/($1)/}glob'{0,1}'x(2*shift)