I am trying to print all valid combination of parentheses in python using my own intuition. It almost worked but just that it doesn't print few combinations. The code looks like this
solution = ""
def parentheses(n):
global solution
if n == 0:
print solution
return
for i in range(1, n+1):
start_index = len(solution)
solution = solution + ( "(" * i + ")" * i )
parentheses(n - i)
solution = solution[:start_index]
if __name__ == "__main__":
n = int(raw_input("Enter the number of parentheses:"))
print "The possible ways to print these parentheses are ...."
parentheses(n)
For n = 3, it prints
( )( )( )
( )( ( ) )
( ( ) )( )
( ( ( ) ) )
It works like this.
In the first iteration
( )( )( ) will be printed, when the call returns to the immediate parent, it will slice of the list where it started to append first which will now be ( ) and run the next iteration of the loop to print ( )( ( ) ) and so on
The problem is I am somehow not able to capture this combination using this logic
( ( )( ) )
While I am thinking on how to fix it, if any python guru can suggest a fix to this, then that will be great. There are alternate solutions, but since I came very close, I want to improve mine.
I think your current version of the logic is a little oversimplified to capture all the possibilities.
This problem boils down to 3 different cases:
To follow that logic, we then need to keep track of the number of open parens we have left to use (no
below), the current string of parens, and the current balance of open vs. closed (curb
below):
def parens(no, s="", curb=0):
# case 1: all open parens used
if no == 0:
if curb == 0:
return [s]
return parens(no, s+")", curb-1)
# case 2: none are currently open
if curb == 0:
return parens(no-1, s+"(", curb+1)
# case 3: one or more are currently open
return parens(no-1, s+"(", curb+1) + parens(no, s+")", curb-1)
This seems like a natural use of memoization. parenthesis(10)
will involve parentheses(6)
and parentheses(4)
, but parentheses(9)
will also involve parentheses(6)
-- so parenthesis(6)
should just be computed once. Also -- it is natural to use sets since that prevents e.g. ()()()
from being counted twice, once as () + ()()
and once as ()() + ()
. This leads to the following code, which either slaps a new pair of parentheses around parentheses generated for n-1
or concatenates the results of two previous calls:
cache = {}
def parentheses(n):
if n == 0:
return set([''])
elif n in cache:
return cache[n]
else:
par = set('(' + p + ')' for p in parentheses(n-1))
for k in range(1,n):
par.update(p+q for p in parentheses(k) for q in parentheses(n-k))
cache[n] = par
return par
For example,
>>> for p in parentheses(3): print(p)
(()())
((()))
()(())
()()()
(())()
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With