在python中打印有效的括号组合_python

我试图用自己的直觉在python中打印所有有效的括号组合。 它几乎起作用，但只是它不会打印很少的组合。 代码看起来像这样

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)

对于n = 3，它打印

（）（）（）
（）（（））
（（））（）
（（（）））

它的工作原理如下。

在第一次迭代中

（）（）（）将被打印，当调用返回到直接父级时，它将首先开始附加的列表的切片现在将是（）并运行循环的下一次迭代以打印（）（（））等等

问题是我在某种程度上无法使用此逻辑捕获此组合

（（）（））

虽然我正在考虑如何解决它，如果任何python大师可以建议修复它，那将是伟大的。 有其他解决方案，但由于我非常接近，我想改进我的。

我认为你当前版本的逻辑有点过于简单，无法捕捉所有可能性。

这个问题归结为3种不同的情况：

我们已经使用了所有的开括号，只需要关闭它们
我们目前没有任何打开的括号，需要在再次关闭之前添加一个括号
我们至少有一个开放，可以打开一个新的或关闭一个。

为了遵循这个逻辑，我们需要跟踪我们剩下要使用的开放数量（下面no ），当前的parens字符串，以及当前开放与关闭的平衡（下面的curb ）：

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)

这似乎是对的自然使用。 parenthesis(10)将包括parentheses(6)和parentheses(4) ，但parentheses(9) 也将包括parentheses(6) - 因此parenthesis(6)应该只计算一次。 此外 - 使用集合是很自然的，因为这会阻止eg ()()()被计数两次，一次作为() + ()() ，一次作为()() + () 。 这导致以下代码，它们围绕为n-1生成的括号绕一对新括号或连接两个先前调用的结果：

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 p in parentheses(3): print(p)

(()())
((()))
()(())
()()()
(())()

在python中打印有效的括号组合

问题描述

1楼

2楼