c# - sacar - Encontrar todas las combinaciones de soportes bien formados

cuantas combinaciones se pueden hacer con 5 numeros sin repetir

Question

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

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

Answer 1

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

Answer 2

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

Answer 3

¿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<String> brackets(int n) {
if(n == 1){
Set<String> s = new HashSet<String>();
s.add("()");
return s;
}else{
Set<String> s1 = new HashSet<String>();
Set<String> s2 = brackets(n - 1);
for(Iterator<String> it = s2.iterator(); it.hasNext();){
String s = it.next();
s1.add("()" + s);
s1.add("(" + s + ")");
s1.add(s + "()");
}
s2.clear();
s2 = null;
return s1;
}
}

Answer 4

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 (n-k-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.

Answer 5

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 <iostream>
#include <set>
using namespace std;
void brackets( int n );
void brackets_aux( int x, const set<string>& input_set, set<string>& output_set );
int main() {
int n;
cout << "Enter n: ";
cin >> n;
brackets(n);
return 0;
}
void brackets( int n ) {
set<string>* set1 = new set<string>;
set<string>* set2;
for( int i = 1; i <= n; i++ ) {
set2 = new set<string>;
brackets_aux( i, *set1, *set2 );
delete set1;
set1 = set2;
}
}
void brackets_aux( int x, const set<string>& input_set, set<string>& 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<string>::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<string>::iterator i = output_set.begin(); i != output_set.end(); i++ ) {
cout << *i << " ";
}
cout << endl;
}

Answer 6

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("}"));
}
}

Answer 7

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:
()
(()) () ()
(())) (() ()) (()) () () (()) () () ()

Answer 8

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<pairs)
Brackets(output + "(", open+1, close, pairs);
if(close<open)
Brackets(output + ")", open, close+1, pairs);
}
}

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.

Answer 9

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

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

Answer 10

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

Answer 11

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<string> 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<string> {"()"};
//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<string>();
//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 ).

Answer 12

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 <iostream>
#include <string>
#include <set>
using namespace System;
using namespace std;
typedef set<string> 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<System::String ^> ^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;
}

Answer 13

Otra respuesta ineficiente pero elegante =>

public static Set<String> permuteParenthesis1(int num)
{
Set<String> result=new HashSet<String>();
if(num==0)//base case
{
result.add("");
return result;
}
else
{
Set<String> temp=permuteParenthesis1(num-1); // storing result from previous result.
for(String str : temp)
{
for(int i=0;i<str.length();i++)
{
if(str.charAt(i)==''('')
{
result.add(insertParen(str, i)); // addinng `()` after every left parenthesis.
}
}
result.add("()"+str); // adding "()" to the beginning.
}
}
return result;
}
public static String insertParen(String str,int leftindex)
{
String left=str.substring(0, leftindex+1);
String right=str.substring(leftindex+1);
return left+"()"+right;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(permuteParenthesis1(3));
}

Answer 14

Un intento con la memorización:

void push_strings(int i, int j ,vector<vector <string>> &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<string> generateParenthesis(int n) {
vector<vector <string>> T(n+10);
T[0] = {""};
for (int i =1; i <=n; ++i){
for(int j=0; j<i; ++j){
push_strings(i,j, T);
}
}
return T[n];
}

Answer 15

Una solución simple F # / OCaml:

let total_bracket n = let rec aux acc = function | 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) in aux "" (n, 0)

Answer 16

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)")
}
""
}

Answer 17

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<pairs:
foo(output+''('', open+1, close, pairs)
if close<open:
foo(output+'')'', open, close+1, pairs)
foo('''', 0, 0, 3)

Answer 18

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)

Answer 19

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 l r 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 n n 0 0
result

Ejemplo:

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

Answer 20

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")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)

Answer 21

Solución simple en C ++:

#include <iostream>
#include <string>
void brackets(string output, int open, int close, int pairs)
{
if(open == pairs && close == pairs)
cout << output << endl;
else
{
if(open<pairs)
brackets(output+"(",open+1,close,pairs);
if(close<open)
brackets(output+")",open,close+1,pairs);
}
}
int main()
{
for(int i=1;i<=3;i++)
{
cout << "Combination for i = " << i << endl;
brackets("",0,0,i);
}
}

Salida:

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

Answer 22

 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);
}

Answer 23

//C program to print all possible n pairs of balanced parentheses
#include<stdio.h>
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<n)
{
str[p]=''{'';
fn(p+1,n;o+1,c);
}
}
}

Answer 24

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)

Answer 25

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

Answer 26

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);
}
}

Answer 27

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

Answer 28

void function(int n, string str, int open, int close)
{
if(open>n/2 || close>open)
return;
if(open==close && open+close == n)
{
cout<<" "<<str<<endl;
return;
}
function(n, str+"(", open+1, close);
function(n, str+")", open, close+1);
}

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