174
правки
Изменения
Нет описания правки
Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $pointer$, $pointer = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $pointer$ на $1$, закрывающую {{---}} уменьшаем на $1$. Если на протяжении всего перебора $pointer$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
check(s):
Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
*$()[()]\{()()[]\}$ {{---}} верно
Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".
{| border="1" cellpadding="3"
*количество способов полностью разделить скобками $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} $
== Алгоритмы генерации ==
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:
Так же с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $n$.
===Получение номера последовательности===
Здесь пусть $n$ — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.
Научимся считать вспомогательную '''динамику''' $d[i][j]$, где $i$ — длина скобочной последовательности (она "полуправильна": всякой закрывающей скобке имеется парная открывающая, но не все открытые скобки закрыты), $j$ — баланс (т.е. разность между количеством открывающих и закрывающих скобок), $d[i][j]$ — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.
Считать эту динамику можно следующим образом. Пусть $d[i][j]$ — величина, которую мы хотим посчитать. Если $i = 0$, то ответ понятен сразу: $d[0][0] = 1$, все остальные $d[0][j] = 0$. Пусть теперь $i > 0$, тогда мысленно переберём, чему был равен последний символ этой последовательности. Если он был равен '(', то до этого символа мы находились в состоянии $(i-1,j-1)$. Если он был равен ')', то предыдущим было состояние $(i-1,j+1)$. Таким образом, получаем формулу:
$d[i][j] = d[i-1][j-1] + d[i-1][j+1]$
(считается, что все значения $d[i][j]$ при отрицательном $j$ равны нулю). Таким образом, эту динамику мы можем посчитать за $O(n^2)$.
Перейдём теперь к решению самой задачи.
Сначала пусть допустимы только скобки '''одного''' типа. Заведём счётчик $\rm depth$ глубины вложенности в скобки, и будем двигаться по последовательности слева направо. Если текущий символ $s[i] (i=0 \ldots 2n-1)$ равен '(', то мы увеличиваем $\rm depth$ на $1$ и переходим к следующему символу. Если же текущий символ равен ')', то мы должны прибавить к ответу $d[2n - i - 1][\rm depth + 1]$, тем самым учитывая, что в этой позиции мог бы стоять символ '(' (который бы привёл к лексикографически меньшей последовательности, чем текущая); затем мы уменьшаем $\rm depth$ на единицу.
Пусть теперь разрешены скобки '''нескольких''' $k$ типов. Тогда при рассмотрении текущего символа $s[i]$ до пересчёта $\rm depth$ мы должны перебирать все скобки, которые меньше текущего символа, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс $\rm ndepth = \rm depth \pm 1$), и прибавлять к ответу количество соответствующих "хвостов" - завершений (которые имеют длину $2n - i - 1$, баланс $\rm ndepth$ и $k$ типов скобок). Утверждается, что формула для этого количества имеет вид:
$d[2n - i - 1][ndepth] \cdot k^{(2n - i - 1 - ndepth) / 2}$
Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из $d[2n - i - 1][{\rm ndepth}]$. Теперь посчитаем, как изменится ответ из-за наличия $k$ типов скобок. У нас имеется $2n - i - 1$ неопределённых позиций, из которых $\rm ndepth$ являются скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет $(2n - i - 1 - {\rm ndepth}) / 2$ пар) могут быть любого из $k$ типов, поэтому ответ умножается на эту степень числа $k$.
== Источники ==
