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.
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
