如何返回n對括號的所有有效組合？

Question

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時，輸出['()()()', '(())()', '((()))']而忽略'()(())'。如何修改代碼以正確輸出所有可能的解決方案？

Answer 1

如果沒有使用遞歸來完成，這看似：

from itertools import permutations 

def valid(test): 
    open, close = 0, 0 
    for c in test: 
    if c == '(': 
     open += 1 
    elif c == ')': 
     close += 1 
     if close > open: 
     return False 
    return True 

def paren(n): 
    perms = set(''.join(p) for p in permutations('(' * n + ')' * n)) 
    return [s for s in perms if valid(s)] 

Answer 2

使用遞歸，多的效率比itertools.permutations：

def paren(n): 
    ps = set(['(' * n + ')' * n]) 
    for i in range(1, n): 
     for a in paren(i): 
      for b in paren(n-i): 
       ps.add(a + b) 
    return ps 

由於中重複遞歸，通過使用functools.lru_cache也可以提高效率。

或者，帶內置記憶化，

def paren(n, known={}): 
    if n in known: 
     return known[n] 
    ps = set(['(' * n + ')' * n]) 
    for i in range(1, n): 
     for f in paren(i, known): 
      for s in paren(n-i, known): 
       ps.add(f + s) 
    known[n] = ps 
    return ps 

Answer 3

看來這個任務歸結爲與N + 1個節點產生的所有可能的樹。讓我們假設另外一對括號整串左右，則N = 3的所有可能的樹會

 
    o 
    | 
    o   ((())) 
    | 
    o 
    | 
    o 

    o 
/\  (())() 
o o 
| 
o 

    o 
/\ 
o o  ()(()) 
    | 
    o 

    o  ()()() 
/|\ 
o o o 

我不能爲你提供的任何代碼，現在（因此CW），而是指this paper - 它似乎正好處理這個問題。

Answer 4

這是一個遞歸生成器，可以生成所有有效的解決方案。與其他答案不同，此函數從不計算需要過濾掉的重複或無效字符串。這幾乎是相同的算法this answer to a previous question，雖然它並不需要非遞歸輔助函數：

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 

Answer 5

對於N == 3，有5種有效組合：（）（）（） （（（））），（（）（）），（（））（）和（）（（））。

遞歸算法是這樣的：

• 加入任何一個離開 或一次一個右括號從左至右構建有效的字符串。
• 基本情況：所有左括號和右括號已被使用（left == n & & right == n）。只需返回一個空字符串。否則：
• 打印左括號如果不是所有的人都被用來 （左< N），並與（N，左+ 1，右）
• 打印調用子問題只有在右括號括號中使用的右側數量 小於左側括號的數量（右側< 左側）。調用子問題（正，左，右+ 1）

這裏是Java代碼：

public static ArrayList<String> parentheses(int n, int left, int right) { 

ArrayList<String> results = new ArrayList<String>(); 

    if (left == n && right == n) { 
    results.add(""); 
    } 

    if (left < n) { 
    ArrayList<String> subResults = parentheses(n, left + 1, right); 
    for (String subResult : subResults) { 
     String newResult = "(" + subResult; 
     results.add(newResult); 
    } 
    } 

    if (left > right) { 
    ArrayList<String> oldResults = parentheses(n, left, right + 1); 
    for (String oldResult : oldResults) { 
     String newResult = ")" + oldResult; 
     results.add(newResult); 
    } 
    } 

    return results; 
} 

最後，與調用遞歸函數：

parentheses(n, 0, 0); 

Answer 6

我是動態編程和遞歸的新手，但這裏是我的解決方案，沒有遞歸。請讓我知道爲什麼它不會工作，或者如果這是一個可以接受的解決辦法：

class Parenthesis(object): 
    def __init__(self, parens): 
     self.parens = parens 
     self.my_valid_parens = { 
           1: ['()'], 
           2: ['()()', '(())'] 
           } 

    def generate_valid_paren(self): 
     if self.parens <= 2: 
      return self.my_valid_parens[self.parens] 

     i = 3 
     while i <= self.parens: 
      new_set = [] 
      for each in self.my_valid_parens[i-1]: 
       new_set += set([each + '()', '()' + each, '(' + each + ')']) 
      self.my_valid_parens[i] = list(new_set) 
      i += 1 

if __name__ == '__main__': 
    num = 4 
    p = Parenthesis(num) 
    p.generate_valid_paren() 
    print p.my_valid_parens[num] 

這裏是我的輸出時，NUM = 3和4分別爲：

3: ['(()())', '()()()', '()(())', '(())()', '((()))'] 

4: ['(()())()', '()(()())', '((()()))', '()()()()', '(()()())', '()()(())', '(()(()))', '()(())()', '((())())', '(())()()', '()(())()', '()((()))', '(((())))', '((()))()']