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