Изменения
Нет описания правки
|id = def1
|definition ='''Скобочная последовательность''' {{---}} класс комбинаторных объектов, представляющих собой последовательность скобочных символов.}}
'''Примеры скобочных последовательностей:'''
*$(())))($
*$)()()))()(()())$
*пусть $S1$, $S2$ {{---}} правильные скобочные последовательности, тогда $S1S2$ есть правильная скобочная последовательность;
}}
'''Примеры правильных скобочный последовательностей:'''
*$((()()()()))$
*$(())(()())$
Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $pointer$, $pointer = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $pointer$ на $1$, закрывающую {{---}} уменьшаем на $1$. Если на протяжении всего перебора $pointer$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
===Псевдокод:===
check(s):
Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
===Примеры скобочных последовательностей с несколькими типами скобок:===
*$()[()]\{()()[]\}$ {{---}} верно
*количество способов полностью разделить скобками $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$ открывающимися скобками:
