Re: Perl Quiz of the Week #23

#!ruby -w
# not to be sent before:  Sat Sep  4 06:50:14 CEST 2004
=begin

parens - prints all possible strings of balanced parenthesis

This is a solution for regular perl qotw #23, see
"http://perl.plover.com/qotw/r/023".

It wants a single integer N in its argv, and prints all sequences of N
sets of balanced parentheses.

There are C(N) such sequences, where C(N) is the N-th Catalan number,
A000108(N).  The Catalan-sequence is a well-known sequence which can be
introduced by a lot of different problems that do not seem equivalent when
you first look at them.  For example, the number of ways a convex polygon
of N+2 sides can be dissected to triangles is exactly C(N).  There is
a remarkable elementary proof for the closed formula of Catalan-numbers.

Here is the first elements of the Catalan-sequence:

C(0) = 1; C(1) = 1; C(2) = 2; C(3) = 5; C(4) = 14; C(5) = 42

The recurrence equation for the sequence is

C(N) = SUM_{0<=k<N} C(k)*C(N - k - 1)

I will generate the strings of parenthesis in a way that's somewhat
related to the above recurrence.  Let S(N) mean the set of all sequences
of N pairs of balanced parens, thus C(N) = |S(N)|.  Now the elements
of S(N) can be generated (exactly once) in the form (A)B where A is
an element of S(k), B is an element of S(N - k - 1), and 0<=k<N.  S(0)
contains only the empty string.

The program does exactly this, memoizing S(k) for all k<=N in the hope
of gaining speed.  This means, however, that for large N's, you have to
wait before the program starts to output the parens.

As this task doesn't involve complicated string manipulation (for which
Perl is still the most suited language), I'll use ruby again.

Get info about ruby 1.8.1 from "http://www.ruby-lang.org/"; read the
Programming Ruby online at "http://www.rubycentral.com/book".

[email protected]

=end


def main;
	1==$*.size or fail "Usage: parens an_integer";
	levels = $*[0].to_i;
	levels<0 and fail "I need a non-negative integer";
	levels==0 and (puts; exit;);
	@p = [[""]];
	(1...levels).each { |n|
		a = [];
		parens(n) { |x| a << x; };
		@p << a;
	};
	parens(levels) { |x| puts x; };
end;

def parens(n);
	(0...n).each { |k|
		@p[k].each { |a|
			@p[n-k-1].each { |b|
				yield("(" + a + ")" + b);
			};
		};
	};
end;

main;


=begin

# The same code without memoization would be even more elegant, but slower of
# course.  

def main;
	1==$*.size or fail "Usage: parens an_integer";
	levels = $*[0].to_i;
	levels<0 and fail "I need a non-negative integer";
	parens(levels) { |x| puts x; };
end;

def parens(n);
	if n==0;
		yield "";
	else;
		(0...n).each { |k|
			parens(k) { |a|
				parens(n - k - 1) { |b|
					yield("(" + a + ")" + b);
				};
			};
		};
	end;
end;

main;

=end


__END__