[SPOILER] Re: Perl Quiz of the Week #23

On Wed, 01 Sep 2004 12:50:14 -0400, Mark Jason Dominus wrote:
> 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.

This is a brute force approach which simply iterates through every
possible solution (within a certain range), and checks to see whether
they are valid. This produces results in reverse lexicographic order.
Since the forms of the first and last results are easily
constructible, these are explicitly used as the range to search.


#!/usr/bin/perl 

use Math::BigInt; 
use strict; 

my($n)=@ARGV;
$n=~/\A\d+\z/
  or die "Usage: $0 <integer>\n";
if(!$n){
  print "\n";
  exit;
}
$n=Math::BigInt->new($n)
  if my $use_big=$n>15;

my $len=$n*2;

# Trim the search space
my $start;
for(my $bit=1<<$len-1;$bit;$bit>>=2){
  $start|=$bit;
}
my $end=(1<<$len)-1^(1<<$len/2)-1;

# Go through every possibility
TRY: for(my $i=$start;$i<=$end;++$i){
  my $str;
  if($use_big){
    ($str=$i->as_bin)=~s/0b//;
    $str=~y/10/()/;
  }else{
    $str=unpack "b$len",pack 'V',$i;
    $str=~y/01/()/;
  }
  my($bal,$pos);
  for(split //,$str){
    $bal+=$_ eq '(' ? 1 : -1;
    next TRY
      if $bal<0
      || $bal>($len-$pos++)
      ;
  }
  print "$str\n";
}

__END__

-- 
	Peter Haworth	[email protected]
"The POP3 server service depends on the SMTP server service, which 
 failed to initialize because of the following error:
 The command completed successfully."	-- Windows NT Server v3.51