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

Question

所以我正在编写一个函数，其中 returns 是所有合法括号的字符串列表，其中恰好有 n 对括号被打开和关闭。括号类型在对列表中以字符串形式给出。

例如：如果对是列表 ["()", "[]"] 函数必须 return 所有有效的 2n 个字符表达式，方括号和圆括号。

注意：如果所有打开的括号也关闭（使用适当的括号）并且括号彼此正确嵌套，则括号表达式有效。 "[] ()" 是有效表达式，而 "[(])" 不是有效表达式。

例如：输入：

print(all_paren(2, ["()","{}"]))

应该return以下列表：

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

我的代码不太成功：

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

输出：

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

{'[]', '()'}

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

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

Find all combinations of parentheses python with recursion

python

python-3.x

recursion

输出：