查找带递归的括号python的所有组合

Question

因此，我正在编写一个函数，它返回所有合法括号的字符串列表，其中打开和关闭了n对括号。括号类型在对列表中以字符串的形式给出。

例如:如果对是list ["()“、”[]“)，则函数必须返回所有有效的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

提前感谢！

Answer 1

使用permutations方法通过itertools构建python

open_close和close_open是字典，open_close映射为闭括号，close_open maps尾括号为开括号。

all_perm()为所提供的括号生成所有排列。

is_val_paren接受一个string并检查括号组合是否有效。

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 = ["()", "[]", "{}"]))

产出：

{'[()]', '()[]', '([])', '[]()', '[[]]', '()()', '[][]', '(())'}

{'[]', '()'}

{'([{}])', '{[]}()', '{[][]}', '{}[]{}', '[({})]', '[]{()}', '(())[]', '{({})}', '[()()]', '[][{}]', '()[{}]', '[()[]]', '[]()[]', '()[()]', '()(())', '()({})', '(([]))', '[(())]', '[([])]', '[{}][]', '(){}{}', '{[]()}', '{{{}}}', '({}[])', '({}){}', '([()])', '{}(){}', '{()()}', '[{{}}]', '[{}{}]', '[(){}]', '(){[]}', '()()[]', '{{}()}', '(){}()', '{}[{}]', '[](){}', '({{}})', '(()){}', '[][][]', '()[]{}', '({})[]', '{}{[]}', '{}[][]', '([]())', '{}[[]]', '[]{{}}', '({()})', '[]([])', '()()()', '[[()]]', '[[]()]', '[](())', '{}{{}}', '{[]{}}', '{}{}[]', '{{}}{}', '()[][]', '([])()', '[()][]', '[{}]{}', '{[[]]}', '([]){}', '{}[()]', '()[[]]', '[{}]()', '{[]}{}', '{{}[]}', '()[]()', '{}{}()', '{(){}}', '({[]})', '{{}{}}', '{()}{}', '[[]]()', '((){})', '[{}[]]', '[()]{}', '[]{}{}', '{{()}}', '([][])', '(()[])', '()([])', '{(())}', '[[]][]', '([]{})', '(())()', '([[]])', '[]{}[]', '[[[]]]', '(){}[]', '[[][]]', '[{}()]', '[][]()', '[[]]{}', '{}(())', '{}({})', '{[()]}', '[()]()', '(){()}', '{}([])', '(){{}}', '[]{}()', '{}()()', '[]()()', '([])[]', '{()}()', '{}{()}', '(({}))', '[[]{}]', '[][()]', '{}[]()', '({}{})', '((()))', '({})()', '{()}[]', '[[{}]]', '()(){}', '[][[]]', '{{}}()', '[{()}]', '{([])}', '[][]{}', '{{}}[]', '({}())', '[{[]}]', '{[{}]}', '{()[]}', '(()())', '{{[]}}', '[]{[]}', '{}()[]', '{}{}{}', '[]({})', '{[]}[]'}