¿Cómo devolver todas las combinaciones válidas de n pares de paréntesis?

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) 

El código anterior es mi bash de resolver el problema indicado. Da soluciones suficientes para n<3 , pero de lo contrario, no da todas las soluciones. Por ejemplo, cuando n=3 , genera ['()()()', '(())()', '((()))'] omitiendo '()(())' . ¿Cómo modifico el código para generar correctamente todas las soluciones posibles?

Aquí hay un generador recursivo que produce todas las soluciones válidas. A diferencia de las otras respuestas, esta nunca calcula cadenas duplicadas o inválidas que necesitan ser filtradas. Este es prácticamente el mismo algoritmo que en esta respuesta a una pregunta anterior , aunque no necesita una función auxiliar no recursiva:

 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 

Si no tiene que hacerse usando la recursividad, esto parece funcionar:

 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)] 

Usando recursión, y mucho más eficiente que itertools.permutations :

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

Debido a la repetida repetición, también se puede hacer más eficiente utilizando functools.lru_cache .

O bien, con la memoria integrada,

 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(ni, known): ps.add(f + s) known[n] = ps return ps 

Soy nuevo en la progtwigción dinámica y la recursión, pero aquí está mi solución sin recursión. Por favor, hágame saber por qué no funciona o si esta es una solución aceptable:

 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] 

Aquí está mi salida para cuando num = 3 y 4 respectivamente:

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

Parece que la tarea se reduce a generar todos los árboles posibles con nodos N + 1. Asummos otro par de parens alrededor de toda la cadena, entonces para N = 3 todos los árboles posibles serán

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

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

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

   o () () ()
  / | \
 ooo

No puedo proporcionarle ningún código en este momento (por lo tanto, CW), pero consulte este documento , parece que trata este problema exactamente.

Para N == 3, hay 5 combinaciones válidas: () () (), ((())), (() ()), (()) () y () (()).

El algoritmo recursivo funciona así:

  • Cree las cadenas válidas de izquierda a derecha agregando un paréntesis izquierdo o derecho a la vez.
  • Caso base: se han utilizado todos los paréntesis izquierdo y derecho (izquierda == n && derecha == n). Solo devuelve una cadena vacía. De otra manera:
  • Imprima un paréntesis izquierdo si no se han utilizado todos (izquierda
  • Imprima un paréntesis derecho solo si el número de paréntesis derechos utilizados es menor que el número de paréntesis izquierdos utilizados (derecha

Aquí está el código de Java:

 public static ArrayList parentheses(int n, int left, int right) { ArrayList results = new ArrayList(); if (left == n && right == n) { results.add(""); } if (left < n) { ArrayList subResults = parentheses(n, left + 1, right); for (String subResult : subResults) { String newResult = "(" + subResult; results.add(newResult); } } if (left > right) { ArrayList oldResults = parentheses(n, left, right + 1); for (String oldResult : oldResults) { String newResult = ")" + oldResult; results.add(newResult); } } return results; } 

Al final, invoca la función recursiva con:

 parentheses(n, 0, 0);