如何返回n对括号的所有有效组合? [英] How to return all valid combinations of n-pairs of parentheses?

问题描述

def paren(n):
    lst = ['(' for x in range(n)]
    current_string = ''.join(lst)
    solutions = list()
    for i in range(len(current_string)+1):
        close(current_string, n, i, solutions)
    return solutions

def close(current_string, num_close_parens, index, solutions):
    """close parentheses recursively"""
    if num_close_parens == 0:
        if current_string not in solutions:
            solutions.append(current_string)
        return
    new_str = current_string[:index] + ')' + current_string[index:]
    if num_close_parens and is_valid(new_str[:index+1]):
        return close(new_str, num_close_parens-1, index+1, solutions)
    else:
        return close(current_string, num_close_parens, index+1, solutions)

def is_valid(part):
    """True if number of open parens >= number of close parens in given part"""
    count_open = 0
    count_close = 0
    for paren in part:
        if paren == '(':
            count_open += 1
        else:
            count_close += 1
    if count_open >= count_close:
        return True
    else:
        return False

print paren(3)

上面的代码是我为解决上述问题所做的尝试.它为n<3提供了足够的解决方案，但否则，它没有给出所有解决方案.例如，当n=3时，它输出['()()()', '(())()', '((()))']而忽略了'()(())'.如何修改代码以正确输出所有可能的解决方案?

The above code is my attempt at solving the stated problem. It gives sufficient solutions for n<3, but otherwise, it doesn't give out all the solutions. For example, when n=3, it outputs ['()()()', '(())()', '((()))'] leaving out '()(())'. How do I modify the code to output all the possible solutions correctly?

推荐答案

这是一个递归生成器，可产生所有有效的解决方案.与其他答案不同，此答案永远不会计算需要过滤掉的重复或无效字符串.该算法与上一个问题的答案几乎相同，尽管它不需要非递归辅助功能:

Here's a recursive generator that yields all valid solutions. Unlike the other answers, this one never calculates duplicated or invalid strings that need to be filtered out. This is pretty much the same algorithm as in this answer to a previous question, though it doesn't need a non-recursive helper function:

def paren(left, right=None):
    if right is None:
        right = left  # allows calls with one argument

    if left == right == 0: # base case
        yield ""

    else:
        if left > 0:
            for p in paren(left-1, right): # first recursion
                yield "("+p

        if right > left:
            for p in paren(left, right-1): # second recursion
                yield ")"+p

这篇关于如何返回n对括号的所有有效组合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！