[SPOILER] Perl Quiz of the Week #23

I ginned up 2 solutions to this quiz. neither are recursive. The first is
perhaps the most obvious of all, simply generate all possible strings and
keep the ones that are correctly balanced.


use Algorithm::Permute;
$total=$ARGV[0];
my %seen;
for(0..$total-1)
  {
    push( @array,"(");
    push( @array,")");
  }

  my $p = new Algorithm::Permute(\@array);
  while (@res = $p->next)
  {
    #print @res, "\n";
    if(&balanced(\@res))
      {
      $j=join("",@res);
      if(! exists $seen{$j})
        {
          push @answer,$j;
          $seen{$j}=1;
        }
      }
  }
foreach(@answer)
  {
    print "$_\n";
  }

sub balanced
  {
    my $line=shift;
    my $unbal=0;
    my $open=0;
    my $close=0;
    foreach(@$line)
      {
      if($_ eq "(")
        {
          $unbal++;
          if($unbal<0)
            {;return 0;}
        }
      if($_ eq ")")
        {
          $unbal--;
          if($unbal<0)
            {;return 0;}
        }
      }
    return 1;
  }


This has O[2n!] running time so it really does not work past n=4, or maybe
5 (if you have a lot of memory and a fast machine). my second solution only
generates matched pairs so it is much faster and has a running time of
O[2^2n] THis is not so bad because the number of answer lines is also
exponential. It also has the virtue of not using a lot of space.

$total=$ARGV[0];

exit unless $total=~m/[0-9]+/;

for(0..2**($total*2-2)-1)
  {
    @choices=split(/ */,sprintf("%.*b",$total*2, $_));
    $unbalanced=0;
    $count=0;
    $open=$total;
    $s="";
    while($count<2*$total)
      {
      if($count<2*$total and !$unbalanced)
        {
          $s=$s."(";
          $unbalanced ++;
          $count++;
          $open--;
        }
      elsif($open and $unbalanced)
        {
          $choice=pop(@choices);
          if($choice eq "0")
            {
            $s=$s.")";
            $unbalanced--;
            $count++;
            }
          elsif($choice eq "1")
            {
            $s=$s."(";
            $unbalanced++;
            $count++;
            $open--;
            }
          else
            {
            print "crap\n";#this should never happen
            $count++;
            }
        }
      else#mustbedone
        {
          while($count<$total*2)
            {
            $s=$s.")";
            $unbalanced--;
            $count++;
            }
        }
      }
    if(! exists $seen{$s})
      {
      print $s,"\n";
      $seen{$s}=1;
      }
  }