Encontrar todas las combinaciones de soportes bien formados

Esto surgió mientras hablaba con un amigo y pensé que podría preguntar aquí, ya que es un problema interesante y me gustaría ver las soluciones de otras personas.

La tarea es escribir una función Corchetes (int n) que imprime todas las combinaciones de corchetes bien formados de 1 … n. Para corchetes (3) la salida sería

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

Hizo una grieta en ello .. C # también.

 public void Brackets(int n) { for (int i = 1; i < = n; i++) { Brackets("", 0, 0, i); } } private void Brackets(string output, int open, int close, int pairs) { if((open==pairs)&&(close==pairs)) { Console.WriteLine(output); } else { if(open 

La recursión se aprovecha del hecho de que nunca puede agregar más corchetes de apertura que la cantidad deseada de pares, y nunca puede agregar más corchetes de cierre que abrir corchetes.

F # :

Aquí hay una solución que, a diferencia de mi solución anterior, creo que puede ser correcta. Además, es más eficiente.

 #light let brackets2 n = let result = new System.Collections.Generic.List<_>() let a = Array.create (n*2) '_' let rec helper lr diff i = if l=0 && r=0 then result.Add(new string(a)) else if l > 0 then a.[i] < - '(' helper (l-1) r (diff+1) (i+1) if diff > 0 then a.[i] < - ')' helper l (r-1) (diff-1) (i+1) helper nn 0 0 result 

Ejemplo:

 (brackets2 4) |> Seq.iter (printfn "%s") (* (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() *) 

El número de combinaciones posibles es el número catalán de N pares C (n).

Este problema se debatió en los foros de joelonsoftware.com de forma bastante imparcial, incluidas las soluciones iterativas, recursivas e iterativas / cambio de bits. Algunas cosas geniales allí.

Aquí hay una solución recursiva rápida sugerida en los foros en C #:

DO#

 public void Brackets(int pairs) { if (pairs > 1) Brackets(pairs - 1); char[] output = new char[2 * pairs]; output[0] = '('; output[1] = ')'; foo(output, 1, pairs - 1, pairs, pairs); Console.writeLine(); } public void foo(char[] output, int index, int open, int close, int pairs) { int i; if (index == 2 * pairs) { for (i = 0; i < 2 * pairs; i++) Console.write(output[i]); Console.write('\n'); return; } if (open != 0) { output[index] = '('; foo(output, index + 1, open - 1, close, pairs); } if ((close != 0) && (pairs - close + 1 <= pairs - open)) { output[index] = ')'; foo(output, index + 1, open, close - 1, pairs); } return; } 

Corchetes (3);

Salida:
()
(()) () ()
(())) (() ()) (()) () () (()) () () ()

Versión de Python de la primera respuesta votada.

 def foo(output, open, close, pairs): if open == pairs and close == pairs: print output else: if open 

Aquí hay otra solución de F #, que favorece la elegancia sobre la eficiencia, aunque la memorización probablemente conduzca a una variante relativamente exitosa.

 let rec parens = function | 0 -> [""] | n -> [for k in 0 .. n-1 do for p1 in parens k do for p2 in parens (nk-1) -> sprintf "(%s)%s" p1 p2] 

De nuevo, esto solo arroja una lista de esas cadenas con exactamente n pares de parens (en lugar de a lo sumo n), pero es fácil de envolver.

F # :

ACTUALIZACIÓN : esta respuesta es incorrecta. Mi N = 4 falla, por ejemplo “(()) (())”. (¿Ves por qué?) En breve publicaré un algoritmo correcto (y más eficiente).

(¡Qué vergüenza para todos ustedes, votantes, por no haberme atrapado! :))


Ineficiente, pero corto y simple. (Tenga en cuenta que solo imprime la ‘enésima’ línea; llame en un bucle desde 1..n para obtener la salida solicitada por la pregunta).

 #light let rec brackets n = if n = 1 then ["()"] else [for s in brackets (n-1) do yield "()" ^ s yield "(" ^ s ^ ")" yield s ^ "()"] 

Ejemplo:

 Set.of_list (brackets 4) |> Set.iter (printfn "%s") (* (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() *) 

Solución simple en C ++:

 #include  #include  void brackets(string output, int open, int close, int pairs) { if(open == pairs && close == pairs) cout < < output << endl; else { if(open 

Salida:

 Combination for i = 1 () Combination for i = 2 (()) ()() Combination for i = 3 ((())) (()()) (())() ()(()) ()()() 

Maldita sea, todos me ganaron, pero tengo un buen ejemplo de trabajo 🙂

http://www.fiveminuteargument.com/so-727707

La clave es identificar las reglas, que en realidad son bastante simples:

  • Construye la cadena char-by-char
  • En un punto dado en la cadena
    • si los corchetes en la cadena hasta el momento se equilibran (incluye str vacíos), agregue un corchete abierto y recurse
    • si se han usado todos los corchetes abiertos, agregue un corchete de cierre y recurse
    • de lo contrario, recurse dos veces, una para cada tipo de corchete
  • Deténgase cuando llegue al final 🙂

Common Lisp:

Esto no los imprime, pero produce una lista de listas de todas las estructuras posibles. Mi método es un poco diferente al de los demás. Reestructura las soluciones brackets(n - 1) manera que se conviertan en brackets(n) . Mi solución no es la cola recursiva, pero podría hacerse con un poco de trabajo.

Código

 (defun brackets (n) (if (= 1 n) '((())) (loop for el in (brackets (1- n)) when (cdr el) collect (cons (list (car el)) (cdr el)) collect (list el) collect (cons '() el)))) 

Una solución simple F # / OCaml:

 dejar total_bracket n =
     let rec aux acc = función
         |  0, 0 -> print_string (acc ^ "\ n")
         |  0, n -> aux (acc ^ ")") (0, n-1)
         |  n, 0 -> aux (acc ^ "(") (n-1, 1)
         |  n, c ->
                 aux (acc ^ "(") (n-1, c + 1);
                 aux (acc ^ ")") (n, c-1)
     en
     aux "" (n, 0)

Aquí hay una solución en C ++. La idea principal que uso es que tomo el resultado del i anterior (donde i es el número de pares de paréntesis), y lo alimento como entrada al siguiente i . Luego, para cada cadena en la entrada, colocamos un par de corchetes en cada ubicación de la cadena. Se agregan nuevas cadenas a un conjunto para eliminar duplicados.

 #include  #include  using namespace std; void brackets( int n ); void brackets_aux( int x, const set& input_set, set& output_set ); int main() { int n; cout < < "Enter n: "; cin >> n; brackets(n); return 0; } void brackets( int n ) { set* set1 = new set; set* set2; for( int i = 1; i < = n; i++ ) { set2 = new set; brackets_aux( i, *set1, *set2 ); delete set1; set1 = set2; } } void brackets_aux( int x, const set& input_set, set& output_set ) { // Build set of bracket strings to print if( x == 1 ) { output_set.insert( "()" ); } else { // For each input string, generate the output strings when inserting a bracket pair for( set::iterator s = input_set.begin(); s != input_set.end(); s++ ) { // For each location in the string, insert bracket pair before location if valid for( unsigned int i = 0; i < s->size(); i++ ) { string s2 = *s; s2.insert( i, "()" ); output_set.insert( s2 ); } output_set.insert( *s + "()" ); } } // Print them for( set::iterator i = output_set.begin(); i != output_set.end(); i++ ) { cout < < *i << " "; } cout << endl; } 
 def @memo brackets ( n ) => [] if n == 0 else around( n ) ++ pre( n ) ++ post( n ) ++ [ "()" * n) ] def @memo pre ( n ) => map ( ( s ) => "()" ++ s, pre ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else [] def @memo post ( n ) => map ( ( s ) => s ++ "()", post ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else [] def @memo around ( n ) => map ( ( s ) => "(" ++ s ++ ")", brackets( n - 1 ) ) 

( Kin , que es algo así como un modelo de actor basado en python lineal con rasgos. No he podido implementar @memo, pero lo anterior funciona sin esa optimización)

Haskell:

Traté de encontrar una lista elegante de una manera simple para esto:

 import Control.Applicative brackets :: Int -> [String] brackets n = f 0 0 where f pos depth = if pos < 2*n then open <|> close else stop where -- Add an open bracket if we can open = if depth < 2*n - pos then ('(' :) <$> f (pos+1) (depth+1) else empty -- Add a closing bracket if we can close = if depth > 0 then (')' :) < $> f (pos+1) (depth-1) else empty -- Stop adding text. We have 2*n characters now. stop = pure "" main = readLn >>= putStr . unlines . brackets 

¿por qué no puede ser tan simple como esto? Esta idea es bastante simple

corchetes (n) -> ‘()’ + corchetes (n-1) 0 ‘(‘ + corchetes (n-1) + ‘)’ 0 corchetes (n-1) + ‘()’

donde 0 es la operación de concatenación anterior

 public static Set brackets(int n) { if(n == 1){ Set s = new HashSet(); s.add("()"); return s; }else{ Set s1 = new HashSet(); Set s2 = brackets(n - 1); for(Iterator it = s2.iterator(); it.hasNext();){ String s = it.next(); s1.add("()" + s); s1.add("(" + s + ")"); s1.add(s + "()"); } s2.clear(); s2 = null; return s1; } } 

Versión Groovy basada en la elegante solución c # de markt anterior. Comprobación dinámica de apertura y cierre (la información se repitió en salida y args), así como la eliminación de un par de verificaciones lógicas extrañas.

 3.times{ println bracks(it + 1) } def bracks(pairs, output=""){ def open = output.count('(') def close = output.count(')') if (close == pairs) { print "$output " } else { if (open < pairs) bracks(pairs, "$output(") if (close < open) bracks(pairs, "$output)") } "" } 

La versión del proveedor C # se basa en el algoritmo de retroceso recursivo, espero que sea útil.

 public List generateParenthesis(int n) { List result = new LinkedList(); Generate("", 0, 0, n, result); return result; } private void Generate(String s, int l, int r, int n, List result){ if(l == n && r == n){ result.add(s); return; } if(l 

No es la solución más elegante, pero así fue como lo hice en C ++ (Visual Studio 2008). Aprovechando el conjunto de STL para eliminar duplicados, simplemente ingenuamente inserto pares nuevos () en cada índice de cadena en cada cadena de la generación anterior, luego recurse.

 #include "stdafx.h" #include  #include  #include  using namespace System; using namespace std; typedef set StrSet; void ExpandSet( StrSet &Results, int Curr, int Max ) { if (Curr < Max) { StrSet NewResults; for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it) { for (unsigned int stri=0; stri < (*it).length(); stri++) { string NewStr( *it ); NewResults.insert( NewStr.insert( stri, string("()") ) ); } } ExpandSet( NewResults, Curr+1, Max ); Results = NewResults; } } int main(array ^args) { int ParenCount = 0; cout < < "Enter the parens to balance:" << endl; cin >> ParenCount; StrSet Results; Results.insert( string("()") ); ExpandSet(Results, 1, ParenCount); cout < < Results.size() << ": Total # of results for " << ParenCount << " parens:" << endl; for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it) { cout << *it << endl; } return 0; } 
 //C program to print all possible n pairs of balanced parentheses #include void fn(int p,int n,int o,int c); void main() { int n; printf("\nEnter n:"); scanf("%d",&n); if(n>0) fn(0,n,0,0); } void fn(int p,int n,into,int c) { static char str[100]; if(c==n) { printf("%s\n",str); return; } else { if(o>c) { str[p]='}'; fn(p+1,n,o,c+1); } if(o 

versión ruby:

 def foo output, open, close, pairs if open == pairs and close == pairs p output else foo(output + '(', open+1, close, pairs) if open < pairs foo(output + ')', open, close+1, pairs) if close < open end end foo('', 0, 0, 3) 
  validParentheses: function validParentheses(n) { if(n === 1) { return ['()']; } var prevParentheses = validParentheses(n-1); var list = {}; prevParentheses.forEach(function(item) { list['(' + item + ')'] = null; list['()' + item] = null; list[item + '()'] = null; }); return Object.keys(list); } 
 public static void printAllValidBracePermutations(int size) { printAllValidBracePermutations_internal("", 0, 2 * size); } private static void printAllValidBracePermutations_internal(String str, int bal, int len) { if (len == 0) System.out.println(str); else if (len > 0) { if (bal < = len / 2) printAllValidBracePermutations_internal(str + "{", bal + 1, len - 1); if (bal > 0) printAllValidBracePermutations_internal(str + "}", bal - 1, len - 1); } } 

Otra respuesta ineficiente pero elegante =>

 public static Set permuteParenthesis1(int num) { Set result=new HashSet(); if(num==0)//base case { result.add(""); return result; } else { Set temp=permuteParenthesis1(num-1); // storing result from previous result. for(String str : temp) { for(int i=0;i 

Un bash con la memorización:

 void push_strings(int i, int j ,vector> &T){ for (int k=0; k< T[j].size(); ++k){ for (int l=0; l< T[i - 1 - j].size(); ++l){ string s = "(" + T[j][k] + ")" + T[i-1 - j][l]; T[i].push_back(s); } } } vector generateParenthesis(int n) { vector> T(n+10); T[0] = {""}; for (int i =1; i < =n; ++i){ for(int j=0; j 
 def form_brackets(n: int) -> set: combinations = set() if n == 1: combinations.add('()') else: previous_sets = form_brackets(n - 1) for previous_set in previous_sets: for i, c in enumerate(previous_set): temp_string = "{}(){}".format(previous_set[:i+1], previous_set[i+1:]) combinations.add(temp_string) return combinations 
 void function(int n, string str, int open, int close) { if(open>n/2 || close>open) return; if(open==close && open+close == n) { cout< <" "< 

Llamador - function(2*brackets, str, 0, 0);

 results = [] num = 0 def print_paratheses(left, right): global num global results # When nothing left, print the results. if left == 0 and right == 0: print results return # pos is the next postion we should insert parenthesis. pos = num - left - right if left > 0: results[pos] = '(' print_paratheses(left - 1, right) if left < right: results[pos] = ')' print_paratheses(left, right - 1) def print_all_permutations(n): global num global results num = n * 2 results = [None] * num print_paratheses(n, n) 

Referencia: permutaciones de paréntesis

Me hicieron esta pregunta en una entrevista hoy.

Siempre salté esta pregunta en Cracking The Coding porque pensé que era una pregunta tonta para una entrevista. El entrevistador no compartió mi opinión, sin embargo.

A continuación se muestra la solución que podría surgir en la entrevista. El entrevistador estaba buscando el método más eficaz que ya se indicó anteriormente. Él me pasó por esta solución.

 //This method is recursive. It simply returns all the possible arrangements by going down //and building all possible combinations of parenthesis arrangements by starting from "()" //Using only "()" for n == 1, it puts one "()" before, one "()" after and one "()" around //each paren string returned from the call stack below. Since, we are adding to a set, the //set ensure that any combination is not repeated. private HashSet GetParens(int num) { //If num < 1, return null. if (num < 1) return null; //If num == 1, there is only valid combination. Return that. if (num == 1) return new HashSet {"()"}; //Calling myself, by subtracting 1 from the input to get valid combinations for 1 less //pair. var parensNumMinusOne = GetParens(num - 1); //Initializing a set which will hold all the valid paren combinations. var returnSet = new HashSet(); //Now generating combinations by using all n - 1 valid paren combinations one by one. foreach (var paren in parensNumMinusOne) { //Putting "()" before the valid paren string... returnSet.Add("()" + paren); //Putting "()" after the valid paren string... returnSet.Add(paren + "()"); //Putting paren pair around the valid paren string... returnSet.Add("(" + paren + ")"); } return returnSet; } 

La complejidad del espacio de otra solución más eficiente es O (1) pero para este es O ( C n ), donde C n es el número catalán .

La complejidad temporal de este código es la misma que la de la otra solución de alto rendimiento, que es igual a O ( C n ).

Cª#

  public static void CombiParentheses(int open, int close, StringBuilder str) { if (open == 0 && close == 0) { Console.WriteLine(str.ToString()); } if (open > 0) //when you open a new parentheses, then you have to close one parentheses to balance it out. { CombiParentheses(open - 1, close + 1, str.Append("{")); } if (close > 0) { CombiParentheses(open , close - 1, str.Append("}")); } }