parens

#!/usr/bin/perl
# Paren Lister by Ryan Whitehurst
#
# --------------------------------------------------------
# This work is hereby released into the Public Domain.
# This applies worldwide. If this is not legally possible,
# the right is granted for anyone to use this work
# for any purpose without any conditions,
# unless such conditions are required by law
# --------------------------------------------------------
#
# This program is used to list all the possible configurations
# of a given number of pairs of parentheses.

use strict;
my $n = $ARGV[0]; # number of pairs of parens
my $x, my $y; # min,max bounds
my @results = (()); # array of valid sets
print "assigned\n";
my $i, my $j;

sub check_parens {
	# checks to see if there are equal ( and ) in array
	my $count; # should be zero at the end
	
	foreach $i (@_) {
		print "\$i is $i\n";
		if($i) { $count+=1; }
		else { $count-=1; }
		print "count is $count\n";
	}
	if($count==0) { return 1; print "return 1\n"}
	else { return 0; print "return 1\n"}
}

# find $x (0b101010...)
for($i=1;$i<=(2*$n);$i+=2) {
	$x+=(2**$i);
	print "\$x is $x\n";
}
print "found x\n";

# find $y (0b111...000)
for($i=(2*$n-1);$i>=$n;$i--) {
	$y+=(2**$i);
	print "\$y is $y\n";
}
print "found y\n";

# generate array of valid sets
for($i=0;($i+$x)<$y;$i++) {
	my @templist = ();
	for($j=0;$j<(2*$n);$j++) {
		if(($x+$i)&(2**$j)) {
		  $results[$i][$j] = 1;
			print "\$results[$i][$j] is $results[$i][$j]\n";
		} else {
			$results[$i][$j] = 0;
			print "\$results[$i][$j] is $results[$i][$j]\n";
		}
		$templist[$j] = $results[$i][$j];
	}
	
	unless(check_parens(@templist)) {
		undef($results[$i][$j]);
		print "undefine \@results[$i]\n";
	}
}
print scalar(@results) . " results\n";

for($i=0;$i<scalar(@results);$i++) {
	my @templist;
	for($j=0;$j<(2*$n);$j++) {
	  $templist[$j] = $results[$i][$j];
	}
	for($j=0;$j<=scalar(@templist);$j++) {
		next unless exists($templist[$j]);
		if($templist[$j]) {
			print "(";
		} else {
			print ")";
		}
	}
	print "\n";
}