Поиск всех комбинаций правильных скобок

Question

Это возникло во время разговора с другом, и я подумал, что спрошу здесь, потому что это интересная проблема и хотел бы увидеть решения других людей.

Задача состоит в том, чтобы написать функцию Brackets (int n), которая печатает все комбинации правильно сформированных скобок от 1 ... n. Для скобок (3) вывод будет

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

Answer 1

почему это так просто, эта идея довольно проста

скобки (n) -> '()' + скобки (n-1) 0 '(' + скобки (n-1) + ')' 0 скобки (n-1) + '()'

где 0 - операция конкатенации выше

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 2

Haskell:

Я попытался придумать элегантный список:

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

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 , что-то вроде линейного питона, основанного на актерской модели с чертами. Я не дошел до реализации @memo, но вышеописанное работает без этой оптимизации)

Answer 4

Вот решение на C ++. Основная идея, которую я использую, заключается в том, что я беру выходные данные из предыдущего i (где i - количество пар скобок) и передаю их в качестве входных данных для следующего я . Затем для каждой строки во входном файле мы помещаем пару скобок в каждом месте строки. Новые строки добавляются в набор для устранения дубликатов.

#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 5

Версия провайдера C #, основанная на рекурсивном алгоритме обратного отслеживания, надеюсь, это полезно.

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 6

Groovy-версия, основанная на элегантном решении Markt c # выше. Динамическая проверка открытия и закрытия (информация была повторена в выходных данных и аргументах), а также удаление нескольких посторонних логических проверок.

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 7

Мне задали этот вопрос сегодня в интервью.

Я всегда пропускал этот вопрос в Cracking The Coding, потому что думал, что это глупый вопрос для интервью. Интервьюер не разделял моего мнения.

Ниже приведено решение, которое я мог бы найти в интервью. Интервьюер искал более эффективный метод, который уже был приведен выше. Он передал меня, хотя для этого решения.

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

---

Пространственная сложность другого более производительного решения O (1), но для этого O ( C _n ), где C _n - Каталонский номер .

Временная сложность этого кода такая же, как и у другого высокопроизводительного решения, аналогичного O ( C _n ).

Answer 8

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)

Ссылка: Перестановки скобок

Answer 9

In 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 10

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