Изменения

*$<tex>(())))($</tex>*$<tex>)()()))()(()())$</tex>

*пусть $<tex>S$ </tex> {{---}} правильная скобочная последовательность, тогда $<tex>(S)$ </tex> есть правильная скобочная последовательность;*пусть $<tex>S1$</tex>, $<tex>S2$ </tex> {{---}} правильные скобочные последовательности, тогда $<tex>S1S2$ </tex> есть правильная скобочная последовательность;

*$<tex>((()()()()))$</tex>*$<tex>(())(()())$</wikitextex> 

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

<wikitex> '''boolean''' check(s: '''string''')

'''for ''' i = 1 '''to ''' length(s) '''if ''' s[i] == '('

'''else'''

'''if ''' counter < 0

'''if ''' counter == 0

'''else'''

 *<wikitextex>*$()[()]\{()()[]\}$ </tex> {{---}} верно*$<tex>[(]\{\})$ </tex> {{---}} неверно

<wikitex>Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так '$<tex>($' \ < '$\ )$'</tex>.Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$<tex>($" \ < "$\ [$" \ < "$\ )$" \ < "$\ ]$".</wikitextex>. ===Примеры лексикографического порядка для $<tex>n$ </tex> и $<tex>k$</tex>, где $<tex>n$ </tex> {{---}} число открывающихся скобок, а $<tex>k$ </tex> {{---}} число видов скобок===<wikitex>{| borderclass="wikitable" !colspan="12" cellpaddingstyle="padding:7px"| <tex>n = 3"</tex> |$n !colspan= "3$" style="padding:7px"||$<tex>k = 1$</tex>

!style="padding:7px"|$<tex>((()))$</tex> !style="padding:7px"||$<tex>(()())$|</tex> !style="padding:7px"|$<tex>(())()$|</tex> !style="padding:7px"|$<tex>()(())$|</tex> !style="padding:7px"|$<tex>()()()$</tex>

{| borderclass="1wikitable" cellpadding="3" !colspan="2" style="padding:7px"|$<tex>n = 2$|</tex> !colspan="2" style="padding:7px"|$<tex>k = 2$</tex>

!style="padding:7px"|$<tex>()[]$</tex> !style="padding:7px"||$<tex>([])$</tex> !style="padding:7px"||$<tex>[()]$|</tex> !style="padding:7px"|$<tex>[]()$</tex>

Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $i = r - l - 1$, то для любого фиксированного $r$ будет ровно $C_i C_{n-1-i}$ способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на $C_n$.</wikitex>===Аналитическая формулаРекурсивный алгоритм получения лексикографического порядка===Пусть нам известно число <wikitextex>$ C_n = \frac{1}{n+1} C_{2n}^{</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n} $</tex> открывающимися скобками:

Для запуска алгоритма необходимо сделать вызов gen(здесь через $C_n^k$ обозначенn, как обычно0, биномиальный коэффициент0, "").*''ans'' - строка, в которой мы считаем ответ*''counter_open'' - количество открывающих скобок в данный момент*''counter_open'' - количество закрывающих скобок в данный момент '''function''' gen (n: '''int''', counter_open: '''int''', counter_close: '''int''', ans: '''string''') '''if''' counter_open + counter_close == 2 <tex>\cdot</tex> n print ans return '''if''' counter_open < n gen(n, counter_open + 1, counter_close, ans + "(") '''if''' counter_open > counter_close gen(n, counter_open, counter_close + 1, ans + ")")

Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $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}$</wikitex>=Генерация следующей скобочной последовательности===

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

'''string''' next(s: '''string''')

'''for ''' i = length(s) '''downto ''' 1 '''if ''' s[i] == '('

'''if ''' counter_close > counter_open

'''else '''

'''if ''' s == ""

'''else'''

'''for ''' j = 1 '''to ''' counter_open

'''for ''' j = 1 '''to ''' counter_close - 1

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

Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:  '''function''' order(n: '''int''')

if n == 0 result(s) else '''for ''' j = 1 '''to ''' n s = s + '(' '''for ''' j = 1 '''to ''' n s = s + ')' result print s t = next(s) '''while''' t != false print s

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

Пусть <tex>n</tex> — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей. Научимся считать вспомогательную динамику $<tex>d[i][j]$</tex>, где $<tex>i$ </tex> — длина скобочной последовательности (она "полуправильная": всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты), $<tex>j$ </tex> — баланс (т.е. разность между количеством открывающих и закрывающих скобок), $<tex>d[i][j]$ </tex> — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.

Считать эту динамику можно следующим образом. Пусть $<tex>d[i][j]$ </tex> — величина, которую мы хотим посчитать. Если $<tex>i = 0$</tex>, то ответ понятен сразу: $<tex>d[0][0] = 1$</tex>, все остальные $<tex>d[0][j] = 0$</tex>. Пусть теперь $<tex>i > 0$</tex>, тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен '(', то до этого символа мы находились в состоянии $<tex>(i-1,j-1)$</tex>. Если он был равен ')', то предыдущим было состояние $<tex>(i-1,j+1)$</tex>. Таким образом, получаем формулу:

$<tex>d[i][j] = d[i-1][j-1] + d[i-1][j+1]$</tex>

(считается, что все значения $<tex>d[i][j]$ </tex> при отрицательном $<tex>j$ </tex> равны нулю). Таким образом, эту динамику мы можем посчитать за $<tex>O(n^2)$</tex>.

'''int''' getNumber(s: '''string''')

'''for ''' i = 0 '''to ''' 2 * n - 1 '''if ''' s[i] == '('

'''else'''

Пусть теперь разрешены скобки $<tex>k$ </tex> типов. Тогда при рассмотрении текущего символа $<tex>s[i]$ </tex> до пересчёта $<tex>\rm depth$ </tex> мы должны перебирать все скобки, которые меньше текущего символа в установленном ранее порядке, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс $<tex>\rm ndepth = \rm depth \pm 1$</tex>), и прибавлять к ответу количество соответствующих "хвостов" - завершений (которые имеют длину $<tex>2n - i - 1$</tex>, баланс $<tex>\rm ndepth$ </tex> и $<tex>k$ </tex> типов скобок). Утверждается, что формула для этого количества имеет вид: <tex>d[2n - i - 1][ndepth] \cdot k^{(2n - i - 1 - ndepth) / 2}</tex>

$Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из <tex>d[2n - i - 1][{\rm ndepth}] </tex>. Теперь посчитаем, как изменится ответ из-за наличия <tex>k</tex> типов скобок. У нас имеется <tex>2n - i - 1</tex> неопределённых позиций, из которых <tex>\cdot k^{rm ndepth</tex> являются скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет <tex>(2n - i - 1 - {\rm ndepth}) / 2}$</tex> пар) могут быть любого из <tex>k</tex> типов, поэтому ответ умножается на эту степень числа <tex>k</tex>.

Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из $d[2n - i - 1][{Сложность данного алгоритма <tex>O(n^2 + n \rm ndepth}]$. Теперь посчитаем, как изменится ответ из-за наличия $cdot k$ типов скобок. У нас имеется $2n - i - 1$ неопределённых позиций, из которых $\rm ndepth$ являются скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет $(2n - i - 1 - {\rm ndepth}) </ 2$ пар) могут быть любого из $k$ типов, поэтому ответ умножается на эту степень числа $k$tex>.

Пусть <tex>n</tex> — количество пар скобок в последовательности. В данной задаче по заданному <tex>k</tex> требуется найти <tex>k</tex>-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей. Как и в предыдущем разделе, посчитаем динамику $<tex>d[i][j]$ </tex> — количество правильных скобочных последовательностей длины $<tex>i$ </tex> с балансом $<tex>j$</tex>.

'''string''' getSequence(n: '''int''', k: '''int''')

'''for ''' i = 0 '''to ''' 2 * n - 1 '''if ''' d[2 * n - (i + 1)][depth + 1] >= \geqslant k

'''else'''

Пусть теперь разрешён не один, а $<tex>k$ </tex> типов скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение $<tex>d[i + 1][\rm ndepth]$ </tex> на величину $<tex>k^{(2n - i - 1 - \rm ndepth) / 2}$</tex>, чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только $<tex>2n - i - 1 - \rm ndepth$</tex>, поскольку $<tex>\rm ndepth$ </tex> скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем). Сложность данного алгоритма <tex>O(n^2 + n \cdot k)</tex>.  == Количество правильных скобочных последовательностей. Числа Каталана == Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.{{Определение|id = def1|definition ='''Числа Каталана''' (англ. ''Catalan number'') {{---}} последовательность чисел, выражающих:*количество не изоморфных упорядоченных бинарных деревьев с корнем и <tex>n + 1</tex> листьями;*количество способов соединения <tex>2n</tex> точек на окружности <tex>n</tex> не пересекающимися хордами;*количество разбиений выпуклого <tex>(n + 2)</tex>-угольника на треугольники не пересекающимися диагоналями;*количество способов полностью разделить скобками <tex>n + 1</tex> множитель;*количество корректных скобочных последовательностей, состоящих из <tex>n</tex> открывающих и <tex>n</tex> закрывающих скобок;}}===Рекурентная формула=== <tex>C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}</tex> Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях. Самой левой открывающей скобке <tex>l</tex> соответствует определённая закрывающая скобка <tex>r</tex>, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим <tex>i = r - l - 1</tex>, то для любого фиксированного <tex>r</tex> будет ровно <tex>C_i C_{n-1-i}</tex> способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на <tex>C_n</tex>. ===Аналитическая формула=== <tex> C_n = \frac{1}{n+1} C_{2n}^{n} </tex> (здесь через <tex>C_n^k</tex> обозначен, как обычно, биномиальный коэффициент). Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером <tex>n \times n</tex> равно <tex>C_{2n}^{n}</tex>. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке <tex>(n - 1) \times (n + 1)</tex>. Но, с другой стороны, любой монотонный путь в решётке <tex>(n - 1) \times (n + 1)</tex> обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке <tex>n \times n</tex>. Монотонных путей в решётке <tex>(n - 1) \times (n + 1)</tex> имеется <tex>C_{2n}^{n-1}</tex>. В результате получаем формулу:

Сложность данного алгоритма $O(<tex> C_n = C_{2n}^{n} - C_{2n}^2 {n-1} = \frac{1}{n+ 1} C_{2n}^{n \cdot k)$. }</wikitextex> == См. также ==*[[Комбинаторные объекты]]*[[Лексикографический порядок]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение номера по объекту]]*[[Получение объекта по номеру]]*[[Получение следующего объекта]]