F#:

Oto rozwiązanie, które, w przeciwieństwie do mojego poprzedniego rozwiązania, uważam, że może być poprawne. Jest również bardziej wydajny.

#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

Przykład:

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

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

Liczba możliwych kombinacji to Liczba katalońska N par C (n).

Ten problem był omawiany na joelonsoftware.com forums dość exentsively zawierające rozwiązania iteracyjne, rekurencyjne i iteracyjne / bitshifting. Całkiem fajne rzeczy.

Oto szybkie rekurencyjne rozwiązanie zaproponowane na forach w C#:

C #

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

Nawiasy (3);

Wyjście:
()
(()) ()()
((())) (()()) (())() ()(()) ()()()

Python wersja pierwszej głosowanej odpowiedzi.

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)

Oto kolejne rozwiązanie F#, faworyzujące elegancję nad wydajnością, chociaż memoizacja prawdopodobnie doprowadziłaby do stosunkowo dobrze działającego wariantu.

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]

Ponownie, daje to tylko listę tych łańcuchów z Dokładnie n par paren (a nie co najwyżej n), ale łatwo ją zawinąć.

F#:

UPDATE : Ta odpowiedź jest błędna. Moje N=4"(())(())". (Czy widzisz dlaczego?) Wkrótce opublikuję poprawny (i bardziej efektywny) algorytm.

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

Przykład:

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

Proste rozwiązanie w 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);
    }
}

Wyjście:

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

Cholera-wszyscy mnie wyprzedzili, ale mam fajny przykład pracy:)

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

Kluczem jest określenie zasad, które są w rzeczywistości dość proste:

• Zbuduj łańcuch znaków char-by-char
• w danym punkcie łańcucha
  • jeśli nawias w łańcuchu do tej pory balansuje (zawiera pusty str), dodaj otwarty nawias i rekurencyjnie
  • jeśli użyto wszystkich otwartych nawiasów, dodaj nawias zamknięty i recurse
  • w przeciwnym razie, rekurencja dwa razy, raz dla każdego typu nawiasu
• Stop jak dojdziesz do końca: -)

Common Lisp:

To nie drukuje ich, ale tworzy listę List wszystkich możliwych struktur. Moja metoda jest nieco inna od innych. Restrukturyzuje rozwiązania do brackets(n - 1) tak, aby stały się brackets(n). Moje rozwiązanie nie jest rekurencyjne, ale można to zrobić przy odrobinie pracy.

Kod

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

Proste rozwiązanie F# / OCaml : {[0]}

Oto rozwiązanie w C++. Główną ideą, której używam, jest to, że biorę wyjście z poprzedniego i (Gdzie i jest liczbą par nawiasów) i przekazuję je jako wejście do następnego i. Następnie dla każdego ciągu wejściowego umieszczamy parę nawiasów w każdym miejscu łańcucha. Nowe ciągi są dodawane do zestawu w celu wyeliminowania duplikatów.

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

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 , który jest czymś w rodzaju modelu aktora opartego na Pythonie liniowym z cechami. Nie mam czasu na implementację @ memo, ale powyższe działa bez tej optymalizacji)

Haskell:

Starałem się wymyślić elegancką listę monad-y sposób na to:

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

Dlaczego to jest tak proste jak to, ten pomysł jest dość prosty

Nawiasy (n) -- > '() ' + nawiasy (n-1) 0 "("+nawiasy (n-1)+") " 0 nawiasy (n-1) + '()'

Gdzie 0 jest operacją konkatenacji powyżej

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

Groovy wersja oparta na eleganckim rozwiązaniu C# firmy markt powyżej. Dynamiczne sprawdzanie otwarcia i zamknięcia (informacje były powtarzane W output i args), a także usuwanie kilku obcych kontroli logicznych.

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

Provider C # w wersji opartej na rekurencyjnym algorytmie backtrackingu, mam nadzieję, że będzie to pomocne.

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

Niezbyt eleganckie rozwiązanie, ale tak zrobiłem w C++ (Visual Studio 2008). Wykorzystując zestaw STL w celu wyeliminowania duplikatów, naiwnie wstawiam nowe pary () do każdego indeksu łańcucha w każdym łańcuchu z poprzedniej generacji, a następnie rekurencyjnie.

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

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

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

Kolejna nieefektywna, ale elegancka odpowiedź = >

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

}

Próba memoizacji:

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

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<<" "<<str<<endl;
        return;
    }
    function(n, str+"(", open+1, close);
    function(n, str+")", open, close+1);
}

Rozmówca - 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)

Odniesienie: permutacje nawiasów

Zadano mi to pytanie w dzisiejszym wywiadzie.

Zawsze pomijałem to pytanie w łamaniu kodu, ponieważ myślałem, że to głupie pytanie na wywiad. Rozmówca nie podzielił jednak mojej opinii.

Poniżej jest rozwiązanie, które mógłbym wymyślić w wywiadzie. Rozmówca patrzył na bardziej wydajną metodę, która jest już podana powyżej. Przeszedł mnie jednak za to rozwiązanie.

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

Złożoność przestrzeni innych więcej rozwiązaniem wykonywalnym jest o(1), ale dla tego jest O(C _n), gdzie C _n jest liczbą katalońską .

Złożoność czasowa tego kodu jest taka sama jak inne rozwiązanie o wysokiej wydajności, które jest takie samo jak O ( C _n).

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