Parenthesis Permutation

April 14th, 2013

Another interesting puzzle:

Parenthesis Permutation

Given N pair of parenthesis. Write an algorithm which would print out all permutations, possible with those parenthesis given that parenthesis are in correct order (i.e. every open parenthesis is matched with closed parenthesis) For .e.g. .. N =3 should give:

()()()

(()())

()(())

(())()

((()))

There are recursive solutions for this you can find just by googling. I thought of a non-recursive solution

Click to view my solution

The basic idea is to construct a Binary Tree, where left node is '(' extra and right node is ')' extra from the current node. Each node has a weight = number of '(' - number of ')'.

We start with a root node '(' at level 0 and create the tree such that the 2N-1 level will contain permutations for N pairs.

Now when constructing the tree, we create a child only if:

Weight of incoming child is not less than 0
When weight >= 0, it should be less than or equal to the numbers of levels to create, so that we have enough parenthesis left to balance the string

Let's take a look at the tree created (string -> weight) for N = 3:

An optimization - the last level is not required since all that is added is a ')'

Now the code. Infact not using a tree at all, just a linked list and traversing in preorder style, using the concepts above of adding a child. I could have used an array instead of linked list, but it suffers from list expansion frequently hence slowing everything down.

	# Using a linked list instead of ruby array to prevent list expansion which would happen very often
	Node = Struct.new(:str, :weight, :level, :next)

	def permute(n)
	max_level = 2*n - 1
	root = last = Node.new('(', 1, 0)
	loop do
	# start from the first node of the linked list
	cur = root
	cur_level = cur.level + 1
	break if cur_level == max_level
	# Append a right child to the end of the linked list
	last = last.next = Node.new(cur.str + '(', cur.weight + 1, cur_level) if add_child?(cur_level, max_level, cur.weight + 1)
	# Append a left child to the end of the linked list
	last = last.next = Node.new(cur.str + ')', cur.weight - 1, cur_level) if add_child?(cur_level, max_level, cur.weight - 1)
	# remove the first node in the list
	root = root.next
	end
	root
	end

	def add_child?(current_level, max_level, weight)
	weight >= 0 && weight <= (max_level - current_level)
	end

	list = permute(3)
	while list
	puts list.str + ')'
	list = list.next
	end

view raw paren_permut.rb hosted with ❤ by GitHub

The code to generate the tree picture is here

Infact the number of permutations for a given N pair form a series called Catalan Numbers . It goes like this:

N=1 P=1
N=2 P=2
N=3 P=5
N=4 P=14
N=5 P=42
N=6 P=132
N=7 P=429
N=8 P=1430
N=9 P=4862
N=10 P=16796
N=11 P=58786
N=12 P=208012
N=13 P=742900
N=14 P=2674440
N=15 P=9694845

algorithms (5)