#!/usr/bin/perl

=begin

Algorithm taken from:

TAOCP - D.Knuth
Vol 4 Fascicle 4 
Generating All Trees 
History of Combinatorial Generation
Algorithm P (Nested parenthesis in lexicographic order)

=cut        

use strict;
use warnings;
use v5.10;

my $n = shift || die "$!: need size";
my ( $l, $r ) = qw! ( ) !;
my $m;
( $m, my @a ) = init( $n, $m );

my $j;

while (1) {
    visit(@a);
    ( $m, @a ) = easy( $m, @a );
    next if ( $a[$m] eq $l );
    ( $m, $j, @a ) = findj( $m, @a );
    last if ( $j == 0 );
    ( $m, @a ) = incj( $m, $j, @a );
}

sub easy {
    my $m = shift;
    my @a = @_;
    $a[$m] = $r;
    if ( $a[ $m - 1 ] eq $r ) {
        $a[ $m - 1 ] = $l, $m--;
    }

    return $m, @a;
}

sub incj {
    my $m = shift;
    my $j = shift;
    my @a = @_;
    $a[$j] = $l;
    $m = 2 * $n - 1;
    return $m, @a;

}

sub findj {
    my $m = shift;
    my @a = @_;
    my $j = $m - 1;
    my $k = 2 * $n - 1;
    while ( $a[$j] eq $l ) {
        $a[$j] = $r, $a[$k] = $l, $j--, $k -= 2;
    }
    return $m, $j, @a;
}

sub init {
    my $n = shift;
    my $m = shift;
    $m = 2 * $n - 1;

    my @a;

    for my $k ( 1 .. $n ) {
        @a[ 2 * $k - 1, 2 * $k ] = ( $l, $r );
    }
    $a[0] = $r;
    return $m, @a;
}

sub visit {
    shift;
    print @_, "\n";
}