Изменения

|definition ='''Скобочная последовательность''' (англ. ''Bracket Sequences'') {{---}} класс комбинаторных объектов, представляющих собой последовательность скобочных символов.}}'''Примеры скобочных последовательностей:'''*$<tex>(())))($</tex>*$<tex>)()()))()(()())$</tex>

|definition ='''Правильная скобочная последовательность''' (анлг. ''Correct Bracket Sequences'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами:

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

'''Примеры правильных скобочный скобочных последовательностей:'''*$<tex>((()()()()))$</tex>*$<tex>(())(()())$</tex>

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

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

'''boolean''' check(s: '''string'''): pointer counter = 0 '''for (''' i = 1; i <= '''to''' length(s); i++): pointer = ('''if''' s[i] == '(')? pointer counter++ : pointer '''else''' counter-- '''if (pointer ''' counter < 0) '''return ''' ''false '' if (pointer '''return''' counter == 0) return true else return false

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

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

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

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

Для того , чтобы определить лексикографический порядок для правильных скобочных последовательностей , надо установить порядок на алфавите, например так '$<tex>($' \ < '$\ )$'</tex>.Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$<tex>($" \ < "$\ [$" \ < "$\ )$" \ < "$\ ]$"</tex>.

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

{| borderclass="1wikitable" !colspan="2" 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>

Алгоритм генерации лексикографического порядка будет предложен ниже. == Количество правильных скобочных последовательностей. Числа Каталана == Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.{{Определение|id = def1|definition =Числа Каталана {{---}} последовательность чисел, выражающих:*количество не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями;*количество способов соединения $2n$ точек на окружности $n$ не пересекающимися хордами;*количество разбиений выпуклого $(n + 2)$-угольника на треугольники не пересекающимися диагоналями;*количество способов полностью разделить скобками $n + 1$ множитель;*количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;}}===Рекурентная формула:=== $C_n Алгоритмы генерации = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}$

Рекуррентную формулу легко ===Рекурсивный алгоритм получения лексикографического порядка===Пусть нам известно число <tex>n</tex>. Надо вывести из задачи о правильных скобочных последовательностях.все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:

Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$Для запуска алгоритма необходимо сделать вызов <tex>\mathrm{gen}(n</tex>, <tex>0</tex>, которая разбивает формулу две части<tex>0</tex>, каждая из которых в свою очередь является правильной скобочной последовательностью<tex>"")</tex>. Поэтому*<tex> \mathtt{ans}</tex> {{---}} строка, если в которой мы обозначим $i = r считаем ответ*<tex> \mathtt{counter\_open}</tex> - l количество открывающих скобок в данный момент*<tex> \mathtt{counter\_close}</tex> - количество закрывающих скобок в данный момент '''function''' gen(n: '''int''', counter_open: '''int''', counter_close: '''int''', ans: '''string'''): '''if''' counter_open + counter_close == 2 * n print(ans) '''return''' '''if''' counter_open < n gen(n, counter_open + 1$, то для любого фиксированного $r$ будет ровно $C_i C_{counter_close, ans + '(') '''if''' counter_open > counter_close gen(n-, counter_open, counter_close + 1-i}$ способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на $C_n$.ans + ')')

$ C_n = \frac{1}{n+1} C_{2n}^{n} $==Генерация следующей скобочной последовательности===

Пусть нам известна строка <tex>s</tex>, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то вывести "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить (здесь через $C_n^k$ обозначенна этом месте мы можем поставить закрывающую скобку, как обычноне нарушив условия правильности скобочной последовательности, биномиальный коэффициентто есть на протяжении проверки на правильность counter должен быть неотрицательным)., заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:

Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $n \times n$ равно $C_{2n}^{n}$. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке $ '''string''' next(s: '''string'''): counter_close = 0 counter_open = 0 '''for''' i = length(n - s) '''downto''' 1) \times '''if''' s[i] == '(n ' counter_open++ '''if''' counter_close > counter_open '''break''' '''else''' counter_close++ 1)$. Но, <font color="Green">// начиная с символа с другой стороны, любой монотонный путь в решётке $индексом "length(n s) - counter_open - 1counter_close" удаляем все символы (индексация с 0) \times </font> remove(s[length(n + 1s)$ обязательно пересекает диагональ- counter_open - counter_close], следовательно, он получен как раз таким способом из какого-либо s[length(причём единственногоs) монотонного пути, пересекающего диагональ, в решётке $n \times n$. Монотонных путей в решётке $(n - 1]) '''if''' s == "" '''return''' "No Solution" '''else''' s = s +') \times ' '''for''' j = 1 '''to''' counter_open s = s + '(n + ' '''for''' j = 1)$ имеется $C_{2n}^{n'''to''' counter_close -1}$. В результате получаем формулу: s = s + ')' '''return''' s

$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$=Получение лексикографического порядка===

===Генерация следующей скобочной последовательности:=== Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:  next'''function''' order(s)n: pointer_close = 0 pointer_open = 0 for (i = length(s); i > 0; i--) if (s[i] == '(''int'''): 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++):'''to''' n

'''for (''' j = 1; j < pointer_close; j++):'''to''' n

print(s) '''while''' next(s) != "No Solution" print(s = next(s)) '''return true'''

Если эта функция после выполнения выводит $true$Также с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution"добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших <tex>n</tex>.

===Получение лексикографического порядка:номера последовательности===

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

order Научимся считать вспомогательную [[Динамическое программирование | динамику]] <tex>d[i][j]</tex>, где <tex>i</tex> — длина скобочной последовательности (n) s = она "полуправильная"; if (n == 0): result(sвсякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты) else for (j = 1; , <tex>j <= n; i++/tex> — баланс (т.е. разность между количеством открывающих и закрывающих скобок) s = s + '('; for (j = 1; j , <= n; tex>d[i++) s = s + ')'; result(s); t = next(s); while (t ][j]</tex> false) result(s); t = next(s); return— количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.

Также с помощью этого алгоритма Считать эту динамику можно получить скобочную последовательность по номеру и номер по скобочной следующим образом. Пусть <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>'('</tex>, то до этого символа мы находились в состоянии <tex>(i-1, добавив сравнение с нужной последовательностью и счетчикj-1)</tex>. Но это далеко не самый оптимальный алгоритм для подобного типа задач и Если он не будет нормально работать для больших $n$был равен <tex>')'</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>.

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

Считать эту динамику можно следующим образом. Пусть $d[i][j]$ — величина, которую мы хотим посчитать. Если $i = 0$, то ответ понятен сразу '''int''' get_number(s: '''string'''): $d[0][0] num = 1$, все остальные $d[0][j] depth = 0$. Пусть теперь $ '''for''' i > = 0$, тогда мысленно переберём, чему был равен последний символ этой последовательности. Если он был равен '(', то до этого символа мы находились в состоянии $(i'to''' 2 * n -1,j-1)$. Если он был равен '''if''')s[i] == ', то предыдущим было состояние $(' depth++ '''else''' num += d[2 * n - i-1,j][depth +1)$. Таким образом, получаем формулу:] depth-- '''return''' num

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

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

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

Сначала пусть допустимы только скобки '''одного''' типа. Заведём счётчик $\rm depth$ глубины вложенности в скобки, и будем двигаться по последовательности слева направо. Если текущий символ $s[i] Сложность данного алгоритма <tex>O(i=0 \ldots 2n-1)$ равен '(', то мы увеличиваем $n^2 + n \rm depth$ на $1$ и переходим к следующему символу. Если же текущий символ равен 'cdot k)', то мы должны прибавить к ответу $d[2n - i - 1][\rm depth + 1]$, тем самым учитывая, что в этой позиции мог бы стоять символ '(' (который бы привёл к лексикографически меньшей последовательности, чем текущая); затем мы уменьшаем $\rm depth$ на единицу</tex>.

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

$d[2n - i - 1][ndepth] \cdot Пусть <tex>n</tex> — количество пар скобок в последовательности. В данной задаче по заданному <tex>k</tex> требуется найти <tex>k^{(2n - i - 1 </tex>- ndepth) / 2}$ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.

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

Здесь пусть $ '''string''' get_sequence(n$ — количество пар скобок в последовательности. В данной задаче по заданному $: '''int''', k$ требуется найти $: '''int'''): depth = 0 s = "" '''for''' i = 0 '''to''' 2 * n - 1 '''if''' d[2 * n - (i + 1)][depth + 1] <tex>\geqslant</tex> k$ s += '(' depth++ '''else''' k -= d[2 * n - (i + 1)][depth + 1] s += ')' depth--ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей. '''return''' s

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

Пусть сначала допустимы только скобки '''одного''' типаСложность данного алгоритма <tex>O(n^2 + n \cdot k)</tex>.

Будем двигаться по символам искомой строки, ==Количество правильных скобочных последовательностей==Количество правильных скобочных последовательностей со скобками одного типа совпадает с $0$-го по $2n - 1$-ый. Как и в предыдущей задаче, будем хранить счётчик $\rm depth$ — текущую глубину вложенности в скобки. В каждой текущей позиции будем перебирать возможный символ - открывающую скобку или закрывающую. Пусть мы хотим поставить сюда открывающую скобку, тогда мы должны посмотреть на значение $d[i + 1][\rm depth + 1]$. Если оно $\ge k$, то мы ставим в текущую позицию открывающую скобку, увеличиваем $\rm depth$ на единицу и переходим к следующему символу. Иначе мы отнимаем от $k$ величину $d[i + 1Числа Каталана | числами Каталана][\rm depth + 1]$, ставим закрывающую скобку и уменьшаем значение $\rm depth$. В конце концов мы и получим искомую скобочную последовательность.

Пусть теперь разрешён не один, а '''$k$ типов''' скобок== См. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение $dтакже ==*[i + 1[Числа Каталана]]*[[\rm ndepthКомбинаторные объекты]$ на величину $k^{(2n - i - 1 - \rm ndepth) / 2}$, чтобы учесть, что ]*[[Лексикографический порядок]]*[[Генерация комбинаторных объектов в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только $2n - i - 1 - \rm ndepth$, поскольку $\rm ndepth$ скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).лексикографическом порядке]]*[[Получение номера по объекту]]*[[Получение объекта по номеру]]*[[Получение следующего объекта]]