Правильные скобочные последовательности
<wikitex>
Содержание
Определения
| Определение: |
| Скобочная последовательность — класс комбинаторных объектов, представляющих собой последовательность скобочных символов. |
Примеры скобочных последовательностей:
- $(())))($
- $)()()))()(()())$
| Определение: |
Правильная скобочная последовательность — частный случай скобочной последовательности, определяющийся следующими образами:
|
Примеры правильных скобочный последовательностей:
- $((()()()()))$
- $(())(()())$
Алгоритм проверки правильности скобочной последовательности
Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $pointer$, $pointer = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $pointer$ на $1$, закрывающую — уменьшаем на $1$. Если на протяжении всего перебора $pointer$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
псевдокод:
check(s):
pointer = 0
for (i = 1; i <= length(s); i++):
pointer = (s[i] == '(')? pointer++ : pointer--
if (pointer < 0)
return false
if (pointer == 0)
return true
else
return false
Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
Примеры скобочных последовательностей с несколькими типами скобок:
- $()[()]\{()()[]\}$ — верно
- $[(]\{\})$ — неверно
В этом случае для проверки надо будет использовать стек.
Лексикографический порядок порядок правильных скобочных последовательностей
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей надо установить порядок на алфавите, например так '$($' < '$)$'. Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".
Примеры лексикографического порядка для $n$ и $k$, где $n$ — число открывающихся скобок, а $k$ — число видов скобок
| $n = 3$ | $k = 1$ | |||
| $((()))$ | $(()())$ | $(())()$ | $()(())$ | $()()()$ |
| $n = 2$ | $k = 2$ | ||
| $()[]$ | $([])$ | $[()]$ | $[]()$ |
Алгоритм генерации лексикографического порядка будет предложен ниже.
Количество правильных скобочных последовательностей. Числа Каталана
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.
| Определение: |
Числа Каталана — последовательность чисел, выражающих:
|
Рекурентная формула:
$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^k$ обозначен, как обычно, биномиальный коэффициент).
Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $n \times n$ равно $C_{2n}^{n}$. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке $(n - 1) \times (n + 1)$. Но, с другой стороны, любой монотонный путь в решётке $(n - 1) \times (n + 1)$ обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке $n \times n$. Монотонных путей в решётке $(n - 1) \times (n + 1)$ имеется $C_{2n}^{n-1}$. В результате получаем формулу:
$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$
Алгоритмы генерации
Генерация следующей скобочной последовательности:
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то — "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
next(s):
pointer_close = 0
pointer_open = 0
for (i = length(s); i > 0; i--)
if (s[i] == '('):
pointer_open++
if (pointer_close > pointer_open)
break
else
pointer_close++
delete(s, length(s) - pointer_open - pointer_close + 1, pointer_close + l)
if (s == ""):
return false
s = s +')'
for (j = 1; j <= pointer_open; j++):
s = s + '('
for (j = 1; j < pointer_close; j++):
s = s + ')'
return true
Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".
Получение лексикографического порядка:
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:
order (n)
s = "";
if (n == 0):
result(s)
else
for (j = 1; j <= n; i++)
s = s + '(';
for (j = 1; j <= n; i++)
s = s + ')';
result(s);
t = next(s);
while (t <> false)
result(s);
t = next(s);
return
Так же с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $n$.
