[SPOILER] solution to QOW #23

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

Here is my solution. It is based on fairly well known results of 
contect-free language's theory which I'm goingo to briefly discuss.

First of all, the laguage of balaced parentheses is generated by the
following context-free grammar:

(1)  S => \epsilon | (S)S

where \epsilon is the empty word. (1) can be explained by saying:

   A string of balanced parentheses is either empy or it starts by an
   open parenthese, followed by a balanced string of parentheses, followed by 
   the closing parenthese correspondig to the first open one, followed 
   again by a string of balanced parentheses.

Remark that this decomposition is unique, this is important in assuring that
the program below generate each given string only one time.

In the program we start with the string 'S' then we repeatedly apply the
rules in (1) in order to generate all proberly-balanced parentheses
string. We discard a string when one of the following conditions arises:

   (a) there are exactly n '(' in the string 
   (b) there are no more 'S' in the string and the length is < 2*n
   (c) there are more than n+1 'S' in the string
   
In case (a) we replace all 'S' by \epsilon and print the string. Strings in
case (b) must obviously be discarded. To prove that
strings in case (c) can be dropped, simply remarks that a string derived by
applications of (1) starting from S satisfy the following:

(2)               # of 'S' <= # of '(' - 1

Then a case (c) string has more than n '(' and can't possibly lead to a
string with exactly n '('.

Here is the program

#!/usr/bin/perl -wl
use strict;

my $n = shift;

my @stack = qw(S);


while (@stack) {
  my $str = pop @stack;
  my $nt = ($str =~ tr!S!S!);
  my $par = (length($str) - $nt)/2;
  
  if ($par == $n) {
    $str =~ s!S!!g;
    print $str;
  }
  elsif ($nt <= $n) {
    if ($nt > 1) {
      (my $new = $str) =~ s!S!!;
      push @stack,$new;
    }
    $str =~ s!S!(S)S!;
    push @stack,$str;
  }
}

__END__

As I haven't had access in the last days to a proper machine, but only to
my 860MHz Pentium III laptop, I'll say nothing about performances, unless
it is to introduce the 'optimized' version below. In this version we avoid
some string copying by pushing in the stack the _references_ to strings
instead of the strings themselves. Moreover, we also push on the stack the
number of 'S' of the string as well as the number of open parenthese, so
that we do not have to calculate them each time. 

Here is this optimized version which, on my laptop, run about 25% faster
than the not optimized one

#!/usr/bin/perl -wl

use strict;

my $n = shift;


my $str = "S";
my @stack = (0,1,\$str);


while (@stack) {
  my $str = pop @stack;
  my $nt = pop @stack;
  my $par = pop @stack;
  
  if ($par == $n) {
    $$str =~ s!S!!g;
    print $$str;
  }
  elsif ($nt <= $n) {
    if ($nt > 1) {
      (my $new = $$str) =~ s!S!!;
      push @stack,$par,$nt-1,\$new;
    }
    $$str =~ s!S!(S)S!;
    push @stack,$par+1,$nt+1,$str;
  }
}


-- 
Leo"TheHobbit" Cacciari