所以我正在撰寫一個函式,它回傳所有合法括號的字串串列,其中恰好 n 對括號被打開和關閉。括號型別在對串列中作為字串給出。
例如:如果對是串列 ["()", "[]"],則該函式必須回傳所有帶方括號和圓括號的有效 2n 字符運算式。
注意:如果所有打開的括號也都關閉(使用適當的括號)并且括號彼此正確嵌套,則括號運算式有效。“[] ()” 是一個有效的運算式,而“[(])” 不是一個有效的運算式。
例如: 輸入:
print(all_paren(2, ["()","{}"]))
應回傳以下串列:
['(())', '()()', '(){}', '({})', '{()}', '{{}}', '{}()', '{}{}']
我的代碼沒有多大成功:
def all_paren(n, pairs):
lst = []
for i in range(len(pairs)):
lst1 = []
generateParentheses(0,0,n,pairs[i][0],pairs[i][1],lst1)
lst.extend(lst1)
return lst
def generateParentheses(openBr, closeBr, n, left_bracket, right_bracket,lst,s=[]):
if closeBr == n:
lst.append(''.join(s))
return
if closeBr < openBr:
s.append(right_bracket)
generateParentheses(openBr, closeBr 1, n,left_bracket,right_bracket,lst,s)
s.pop()
if openBr < n:
s.append(left_bracket)
generateParentheses(openBr 1, closeBr, n,left_bracket,right_bracket,lst,s)
s.pop()
return
提前致謝!
uj5u.com熱心網友回復:
使用permutations
方法 build into python 通過itertools
open_close
并且close_open
是字典open_close
將左括號映射到右括號,將右括號映射到左close_open maps
括號。
all_perm()
為提供的括號生成所有排列。
is_val_paren
接受 astring
并檢查括號組合是否有效。
import itertools
open_close = dict(
{'(':')',
'[':']',
'{':'}',
'<':'>'
}
)
close_open = dict(
{')':'(',
']':'[',
'}':'{',
'>':'<'
}
)
def all_perm(n, values):
valid_parens = []
for parens in itertools.product(values, repeat = n):
val = list()
for v in parens:
val.extend(v)
#print(f"{val}")
for perm in itertools.permutations(range(n*2)):
brakets = [None]*(n*2)
for index, p in enumerate(perm):
brakets[index] = val[p]
#print(f"{perm=} {brakets=}")
if is_val_paren(brakets):
valid_parens.append(''.join(brakets))
return set(valid_parens)
def is_val_paren(brakets:list):
stack = list()
for braket in brakets:
if braket in open_close.keys():
stack.append(braket)
else:
if len(stack) == 0:
return False
elif stack[-1] == close_open[braket]:
stack.pop()
else:
return False
return len(stack) == 0
print(all_perm(n = 2, values = ["()", "[]"]))
print()
print(all_perm(n = 1, values = ["()", "[]"]))
print()
print(all_perm(n = 3, values = ["()", "[]", "{}"]))
輸出:
{'[()]', '()[]', '([])', '[]()', '[[]]', '()()', '[][]', '(())'}
{'[]', '()'}
{'([{}])', '{[]}()', '{[][]}', '{}[]{}', '[({})]', '[]{()}', '(())[]', '{({})}', '[()()]', '[][{}]', '()[{}]', '[()[]]', '[]()[]', '()[()]', '()(())', '()({})', '(([]))', '[(())]', '[([])]', '[{}][]', '(){}{}', '{[]()}', '{{{}}}', '({}[])', '({}){}', '([()])', '{}(){}', '{()()}', '[{{}}]', '[{}{}]', '[(){}]', '(){[]}', '()()[]', '{{}()}', '(){}()', '{}[{}]', '[](){}', '({{}})', '(()){}', '[][][]', '()[]{}', '({})[]', '{}{[]}', '{}[][]', '([]())', '{}[[]]', '[]{{}}', '({()})', '[]([])', '()()()', '[[()]]', '[[]()]', '[](())', '{}{{}}', '{[]{}}', '{}{}[]', '{{}}{}', '()[][]', '([])()', '[()][]', '[{}]{}', '{[[]]}', '([]){}', '{}[()]', '()[[]]', '[{}]()', '{[]}{}', '{{}[]}', '()[]()', '{}{}()', '{(){}}', '({[]})', '{{}{}}', '{()}{}', '[[]]()', '((){})', '[{}[]]', '[()]{}', '[]{}{}', '{{()}}', '([][])', '(()[])', '()([])', '{(())}', '[[]][]', '([]{})', '(())()', '([[]])', '[]{}[]', '[[[]]]', '(){}[]', '[[][]]', '[{}()]', '[][]()', '[[]]{}', '{}(())', '{}({})', '{[()]}', '[()]()', '(){()}', '{}([])', '(){{}}', '[]{}()', '{}()()', '[]()()', '([])[]', '{()}()', '{}{()}', '(({}))', '[[]{}]', '[][()]', '{}[]()', '({}{})', '((()))', '({})()', '{()}[]', '[[{}]]', '()(){}', '[][[]]', '{{}}()', '[{()}]', '{([])}', '[][]{}', '{{}}[]', '({}())', '[{[]}]', '{[{}]}', '{()[]}', '(()())', '{{[]}}', '[]{[]}', '{}()[]', '{}{}{}', '[]({})', '{[]}[]'}
轉載請註明出處,本文鏈接:https://www.uj5u.com/caozuo/470937.html
標籤:Python python-3.x 递归
上一篇:匿名遞回函式