#!/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 valid combinations   #
#   of a given number of pairs of parentheses.                       #
######################################################################

use strict;

my $begin = time();

die("No args") unless($ARGV[0]);

my $n = $ARGV[0]; # number of pairs of parens
my $min, my $max; # min and max values for algorithm
my @results = ();

sub valid_parens {
	# checks to see if there are equal ( and ) in the array
	my $count = 0; # should end at zero
	my $num = @_[0];
	print "\$num is $num\n";
	my @array = ();

  for(my $i=0;$i<2*$n;$i++) {
		# assigns each bit to the array
		#print("\$num is $num, 2**\$i is " . 2**$i . ", and is " . $num & 2**$i . "\n");
		push(@array,($num & 2**$i ? 1 : 0));
		print "\$array[$i] = $array[$i]\n";
		$array[$i] ? ++$count : --$count;
		print "count is $count\n";
	}

	$count ? return @array : return "\0";
}

# generate minimum value (101010...)
for(my $i=1;$i<2*$n;$i+=2) {
	$min+=2**$i;
	print "\$min is $min, \$i is $i\n";
}

# generate maximum value (111...000)
for(my $i=(2*$n)-1;$i>=$n;$i--) {
	$max+=2**$i;
	print "\$max is $max, \$i is $i\n";
}

# generate array of valid combos
for(my $i=$min;$i<=$max;$i++) {
	push(@results, valid_parens($i));
}

# print results
while(scalar(@results)) {
	print pop(@results) . "\n";
#	pop(@results) == 1 ? print "(" : ")";
}

print "\n\n " . time()-$begin . " seconds elapsed.\n";

__END__
# print results
foreach my @array (@results) {
	foreach my $pt (@array) {
		$pt ? print "(" : print ")";
	}
	print "\n";
}