Trouver toutes les combinaisons de bien-formé entre parenthèses

A pris une fissure à elle.. C# aussi.

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 récursivité est en train de profiter du fait que vous ne pouvez jamais ajouter plus de l'ouverture des crochets que le nombre de paires, et vous ne pouvez pas ajouter plus de crochets de clôture de l'ouverture des crochets..

F#:

Voici une solution qui, contrairement à ma précédente solution, je crois que peut-être raison. Aussi, il est plus efficace.

#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

Exemple:

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

(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)

Voici un autre F# solution, privilégiant l'élégance par rapport à l'efficacité, bien que memoization conduirait probablement à une relativement bien l'exécution de la variante.

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]

Encore une fois, cela ne donne une liste de ces chaînes avec exactement n paires de parenthèses (plutôt qu'au plus n), mais il est facile pour l'envelopper.

La solution la plus 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);
    }
}

De sortie:

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

Common Lisp:

Cela n'a pas l'impression, mais ne produire une liste de listes de toutes les structures possibles. Ma méthode est un peu différente de celle des autres. Il restructure les solutions à brackets(n - 1) tels qu'ils deviennent brackets(n). Ma solution n'est pas de queue récursive, mais il peut être fait avec un peu de travail.

Code

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

Un simple F#/OCaml solution :

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)

Haskell:

J'ai essayé de venir avec un élégant liste monade-y de façon à ce:

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

Groovy version basée sur le markt élégant c# solution ci-dessus. Le contrôle dynamique de d'ouvrir et de fermer (l'information a été répété en sortie et args) ainsi que la suppression d'un couple d'étrangers logique des contrôles.

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

Pas la solution la plus élégante, mais c'était la façon dont je l'ai fait en C++ (Visual Studio 2008). Tirant parti de la STL ensemble afin d'éliminer les doublons, j'ai juste naïvement insérer de nouvelles () paires dans chaque chaîne index dans chaque chaîne de la génération précédente, puis, de manière récursive.

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

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

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

Une tentative avec memoization:

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

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

De l'appelant - function(2*brackets, str, 0, 0);

J'ai été demandé à cette question dans une interview aujourd'hui.

J'ai toujours ignoré cette question dans Les Fissures de Codage parce que je pensais que c'est une question idiote pour une entrevue. L'interviewer n'a pas de partager mon avis cependant.

Ci-dessous est la solution que j'ai pu arriver à l'entrevue. L'interviewer était à la recherche à la plus performante de la méthode qui est déjà donné ci-dessus. Il m'a passé, bien que pour cette solution.

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

L'espace de la complexité de l'autre plus performant solution est O(1), mais l'un est O(C_n), où C_n est Catalan Nombre.

La complexité du temps de ce code est le même que l'autre à haute performance de la solution, qui est la même que O(C_n).