Действительная перестановка скобок

Возможный дубликат:
Решение рекурсивной проблемы (код ката)

дать алгоритм для нахождения всех допустимых перестановок скобок для данного n например:

for n=3, O/P should be
{}{}{} 
{{{}}}
{{}}{} 
{}{{}} 
{{}{}}

Ответы

Ответ 1

Обзор проблемы

Это классическая комбинаторная проблема, которая проявляется по-разному. Эти проблемы по существу идентичны:

  • Создание всех возможных способов балансировки пар круглых скобок N (т.е. этой проблемы)
  • Создание всех возможных способов применения бинарного оператора к N+1 факторам
  • Генерация всех полных двоичных деревьев с N+1 оставляет
  • Многие другие...

См. также

Прямое рекурсивное решение

Здесь простой рекурсивный алгоритм для решения этой проблемы в Java:

public class Parenthesis {
    static void brackets(int openStock, int closeStock, String s) {
        if (openStock == 0 && closeStock == 0) {
            System.out.println(s);
        }
        if (openStock > 0) {
            brackets(openStock-1, closeStock+1, s + "<");
        }
        if (closeStock > 0) {
            brackets(openStock, closeStock-1, s + ">");
        }
    }
    public static void main(String[] args) {
        brackets(3, 0, "");
    }
}

Вышеприведенные отпечатки (как видно на ideone.com):

<<<>>>
<<><>>
<<>><>
<><<>>
<><><>

Дерево рекурсии для n = 3

По существу, мы отслеживаем, сколько открытых и закрытых круглых скобок "доступно" для использования нами при построении строки рекурсивно.

  • Если ничего нет в наличии, строка полностью построена, и вы можете просто распечатать ее
  • Если на складе имеется открытая скобка, попробуйте добавить ее.
    • Теперь у вас есть одна открытая скобка, но еще одна закрывающая скобка для ее баланса.
  • Если на складе имеется закрытая скобка, попробуйте добавить ее.
    • Теперь у вас есть одна менее близкая скобка

Обратите внимание: если вы поменяете порядок рекурсии таким образом, что вы пытаетесь добавить закрывающую скобку, прежде чем пытаться добавить открытую скобку, вы просто получите тот же список сбалансированных круглых скобок, но в обратном порядке! (см. на ideone.com).

"Оптимизированный" вариант

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

Самая важная оптимизация - в аспекте построения строки. Хотя это выглядит как простая конкатенация строк на поверхности, в приведенном выше решении фактически есть "скрытый" компонент построения строки O(N^2) (поскольку конкатенация одного символа на неизменяемый String длины N является операцией O(N)), Как правило, мы оптимизируем это, используя вместо этого переменный StringBuilder, но для этого конкретного случая мы также можем просто использовать переменную char[] и index с фиксированным размером.

Мы также можем оптимизировать, упростив дерево рекурсии. Вместо того, чтобы рекурсировать "оба пути", как в исходном решении, мы можем просто повторить "один путь" и сделать "другой путь" итеративно.

В дальнейшем мы выполнили обе оптимизации, используя char[] и index вместо String, и рекурсивно добавляем открытые круглые скобки, добавляя тесные круглые скобки итеративно: (см. также на ideone.com)

public class Parenthesis2 {
    public static void main(String[] args) {
        brackets(4);
    }
    static void brackets(final int N) {
        brackets(N, 0, 0, new char[N * 2]);
    }
    static void brackets(int openStock, int closeStock, int index, char[] arr) {
        while (closeStock >= 0) {
            if (openStock > 0) {
                arr[index] = '<';
                brackets(openStock-1, closeStock+1, index+1, arr);
            }
            if (closeStock-- > 0) {
                arr[index++] = '>';
                if (index == arr.length) {
                    System.out.println(arr);
                }
            }
        }
    }
}

Логика рекурсии теперь менее очевидна, но две методики оптимизации являются поучительными.

Связанные вопросы

Ответ 2

Пока не является фактическим алгоритмом, хорошей отправной точкой является каталонский номер:

Ссылка

Ответ 3

Эрик Липперт недавно написал об этом в своей статье Every Tree There. Статья ссылается на код, написанный в предыдущей статье Every Binary Tree There.

Если вы можете перечислить все двоичные деревья, то оказывается, что вы можете перечислить все решения десятков различных эквивалентных задач.

Ответ 4

Нерекурсивное решение в Python:

#! /usr/bin/python

def valid(state,N):
    cnt=0
    for i in xrange(N):
        if cnt<0:
            return False
        if (state&(1<<i)):
            cnt+=1
        else:
            cnt-=1
    return (cnt==0)

def make_string(state,N):
    ret=""
    for i in xrange(N):
        if state&(1<<i):
            ret+='{'
        else:
            ret+='}'
    return ret

def all_permuts(N):
    N*=2
    return [make_string(state,N) for state in xrange(1<<N) if valid(state,N)]

if __name__=='__main__':
    print "\n".join(all_permuts(3))

Это в основном рассматривает двоичное представление каждого числа в [0,2 ^ n), рассматривая "1" как "{" и "0" как "}", а затем отфильтровывает только те, которые должным образом сбалансирован.