I want to generate all possible permutations of a set of parentheses of a certain length N.
Example:
if N = 1
Output: ['()']
if N = 3
Output: ['()(())', '(())()', '(()())', '((()))', '()()()']
CodePudding user response:
Credit: https://prepinsta.com/python-program/generate-all-combinations-of-balanced-parentheses/
def generateParenthesis(n, Open, close, s, ans):
if Open == n and close == n:
ans.append(s)
return
if Open < n:
generateParenthesis(n, Open 1, close, s "(", ans)
if close < Open:
generateParenthesis(n, Open, close 1, s ")", ans)
n = 3
ans = []
generateParenthesis(n, 0, 0, "", ans)
for s in ans:
print(s)
CodePudding user response:
As a fresher I came up with this solution where I create all the possible combinations using the function generate_permutations
and then create a new list with only valid parentheses:
def generate_permutations(current, perms, prefix=''):
if len(current) == 0:
perms.add(prefix)
for i in range(len(current)):
new_prefix = prefix current[i]
new_current = current[:i] current[i 1:]
generate_permutations(new_current, perms, new_prefix)
return perms
def refine(l):
os = list()
cs = list()
res = list()
for each in l:
flag = True
for e in each:
if e == '(':
os.append(e)
elif e == ')':
cs.append(e)
if os and os[-1] == '(':
os = os[:-1]
cs = cs[:-1]
else:
flag = False
break
if flag:
res.append(each)
return res
N = 3
string = "()" * N
answer_list = generate_permutations(string, set())
refined = refine(answer_list)
print(refined)