Изменения

</wikitex>

== Алгоритм проверки правильности скобочной последовательности ==

Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $counter$, $counter = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $counter$ на $1$, закрывающую {{---}} уменьшаем на $1$. Если на протяжении всего перебора $counter$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.

===Псевдокод===

check(s)

counter = 0

Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:

===Примеры скобочных последовательностей с несколькими типами скобок===

*$()[()]\{()()[]\}$ {{---}} верно

*$[(]\{\})$ {{---}} неверно

В этом случае для проверки надо будет использовать стек.

== Лексикографический порядок порядок правильных скобочных последовательностей ==

Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так '$($' < '$)$'.

Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".

===Примеры лексикографического порядка для $n$ и $k$, где $n$ {{---}} число открывающихся скобок, а $k$ {{---}} число видов скобок===

{| border="1" cellpadding="3"

|$n = 3$||$k = 1$

Алгоритм генерации лексикографического порядка будет предложен ниже.

== Количество правильных скобочных последовательностей. Числа Каталана ==

Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.

{{Определение

*количество способов полностью разделить скобками $n + 1$ множитель;

*количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;}}

===Рекурентная формула===

$C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}$

Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $i = r - l - 1$, то для любого фиксированного $r$ будет ровно $C_i C_{n-1-i}$ способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на $C_n$.

===Аналитическая формула===

$ C_n = \frac{1}{n+1} C_{2n}^{n} $

$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$

== Алгоритмы генерации ==

===Генерация следующей скобочной последовательности===

Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить, заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:

Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".

===Получение лексикографического порядка===

Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:

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

===Получение номера последовательности===

Пусть $n$ — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.

Сложность данного алгоритма $O(n^2 + n \cdot k)$.

===Получение k-й последовательности===

Пусть $n$ — количество пар скобок в последовательности. В данной задаче по заданному $k$ требуется найти $k$-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.

s = ""

for i = 0 to 2 * n - 1

s += '('

depth++

else

s += ')'

depth--

Сложность данного алгоритма $O(n^2 + n \cdot k)$.

== Источники ==

* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Скобочные последовательности, Материал из Википедии — свободной энциклопедии]

[[Категория: Комбинаторика ]]