Поиск всех комбинаций правильных скобок - PullRequest
Новая
       45

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

32 голосов
/ 08 апреля 2009

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

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

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

Ответы [ 28 ]

49 голосов
/ 08 апреля 2009

Взял трещину в этом .. C # также. 

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

В рекурсии используется тот факт, что вы никогда не сможете добавить больше открывающих скобок, чем требуемое количество пар, и вы никогда не сможете добавить больше закрывающих скобок, чем открывающих скобок.

9 голосов
/ 08 апреля 2009

F # :

Вот решение, которое, в отличие от моего предыдущего решения, я считаю правильным. Кроме того, это более эффективно. 

#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

Пример: 

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

(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
8 голосов
/ 21 ноября 2012

Python версия первого проголосовавшего ответа. 

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)
8 голосов
/ 08 апреля 2009

Число возможных комбинаций: Каталонское число из N пар C (n).

Эта проблема обсуждалась на форумах joelonsoftware.com довольно широко, включая итеративные, рекурсивные и итеративные / бит-смещающие решения. Там есть несколько классных вещей.

Вот быстрое рекурсивное решение, предложенное на форумах в 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;
}

Кронштейны (3);

Выход:
()
(()) () ()
((())) (() ()) (()) () () (()) () () ()

5 голосов
/ 08 апреля 2009

Вот еще одно решение F #, предпочитающее элегантность, а не эффективность, хотя запоминание, вероятно, приведет к относительно хорошо работающему варианту. 

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]

Опять же, это дает только список этих строк с точно n парами паренсов (а не самое большее n), но его легко обернуть.

4 голосов
/ 06 августа 2010

Простое решение в 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);
    }
}

Выход: 

Combination for i = 1
()
Combination for i = 2
(())
()()
Combination for i = 3
((()))
(()())
(())()
()(())
()()()
4 голосов
/ 08 апреля 2009

F # :

ОБНОВЛЕНИЕ : этот ответ неверный. Мой N = 4 промахов, например "(()) (())". (Вы понимаете, почему?) В скором времени я опубликую правильный (и более эффективный) алгоритм.

(Позор всем, кто вы, избиратели, не поймали меня! :))

Неэффективно, но коротко и просто. (Обратите внимание, что он печатает только n-ю строку; вызов в цикле из 1..n, чтобы получить вывод, запрошенный вопросом.) 

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

Пример: 

Set.of_list (brackets 4) |> Set.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
3 голосов
/ 14 апреля 2009

Common Lisp:

Это не печатает их, но создает список списков всех возможных структур. Мой метод немного отличается от других. Это реструктурирует решения для brackets(n - 1) так, что они становятся brackets(n). Мое решение не хвостовое рекурсивное, но оно может быть сделано с небольшой работой.

Код 

(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))))
3 голосов
/ 08 апреля 2009

Блин - все били меня этим, но у меня есть хороший рабочий пример:)

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

Ключ идентифицирует правила, которые на самом деле довольно просты:

  • Построить строку char-by-char
  • В заданной точке строки
    • если скобки в строке до сих пор балансируют (включая пустую строку), добавьте открытую скобку и введите значение
    • если все открытые скобки были использованы, добавить закрывающую скобку и повторить
    • в противном случае, выполнить повторение дважды, по одному разу для каждого типа скобок
  • Остановитесь, когда дойдете до конца: -)
2 голосов
/ 10 апреля 2009

Простое решение 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)

Страница:
...