Изменения

|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>

Алгоритм == Алгоритмы генерации лексикографического порядка будет предложен ниже.==

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

Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами КаталанаДля запуска алгоритма необходимо сделать вызов <tex>\mathrm{gen}(n</tex>, <tex>0</tex>, <tex>0</tex>, <tex>"")</tex>.*<tex> \mathtt{{Определение|id = def1|definition =Числа Каталана ans}</tex> {{---}} последовательность чиселстрока, выражающих:в которой мы считаем ответ*<tex> \mathtt{counter\_open}</tex> - количество не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями;открывающих скобок в данный момент*<tex> \mathtt{counter\_close}</tex> - количество способов соединения $2n$ точек на окружности $закрывающих скобок в данный момент '''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, counter_close, ans + 2'(')$-угольника на треугольники не пересекающимися диагоналями;*количество способов полностью разделить скобками $ '''if''' counter_open > counter_close gen(n , counter_open, counter_close + 1$ множитель;*количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;}}===Рекурентная формула:===ans + ')')

$C_n = Если есть возможность поставить открывающую скобку, то мы ставим её. Аналогично после этого если есть возможность поставить закрывающую скобку, то после этого мы ставим и её.<br>Таким образом строки будут выведены в лексографическом порядке, так как сначала мы мы пытаемся поставить открывающую скобку. При этом мы перебираем все возможные варианты последующих скобок для каждого возможного префикса <tex>\sum_mathtt{i = 0ans}^{n - 1} C_i C_{n - 1 - i}$</tex>, а следовательно в результате получаем все возможножные правильные скобочные последовательности

Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$Пусть нам известна строка <tex>s</tex>, которая разбивает формулу две части, каждая из которых в свою очередь является правильной скобочной последовательностьюпредставляющая собой правильную скобочную последовательность. ПоэтомуНам необходимо вывести следующую скобочную последовательность, а если мы обозначим $i = r - l - 1$ее нет, то для любого фиксированного $r$ будет ровно $C_i C_{n-1-i}$ способоввывести "No solution". Суммируя это по всем допустимым iЧтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить (на этом месте мы и получаем рекуррентную зависимость можем поставить закрывающую скобку, не нарушив условия правильности скобочной последовательности, то есть на $C_n$.протяжении проверки на правильность counter должен быть неотрицательным), заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:

'''string''' next(s: '''string'''): counter_close = 0 counter_open = 0 '''for''' i = length(s) '''downto''' 1 '''if''' s[i] =='(' counter_open++ '''if''' counter_close > counter_open '''break''' '''else''' counter_close++ <font color="Green">// начиная с символа с индексом "length(s) - counter_open - counter_close" удаляем все символы (индексация с 0)</font> remove(s[length(s) - counter_open - counter_close], s[length(s) - 1]) '''if''' s =Аналитическая формула:="" '''return''' "No Solution" '''else''' s = s +')' '''for''' j = 1 '''to''' counter_open s = s + '(' '''for''' j =1 '''to''' counter_close - 1 s =s + ')' '''return''' s

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

(здесь через $C_n^k$ обозначен, как обычно, биномиальный коэффициент)Пусть нам известно число <tex>n</tex>.Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:

Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $n \times n$ равно $C_{2n}^{n}$. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке $ '''function''' order(n - : '''int'''): s = "" '''for''' j = 1) \times ('''to''' n s = s + 1)$. Но, с другой стороны, любой монотонный путь в решётке $'(n - ' '''for''' j = 1) \times ('''to''' n s = s + 1')$ обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо ' print(причём единственногоs) монотонного пути, пересекающего диагональ, в решётке $n \times n$. Монотонных путей в решётке $ '''while''' next(n - 1s) \times != "No Solution" print(n + 1s = next(s))$ имеется $C_{2n}^{n-1}$. В результате получаем формулу: '''return'''

$ C_n = C_{2n}^{Также с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших <tex>n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$</tex>.

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

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

Считать эту динамику можно следующим образом. Пусть нам известна строка $s$<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--}} "No solution"1)</tex>. Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобкуЕсли он был равен <tex>')'</tex>, которую можно заменить то предыдущим было состояние <tex>(i-1, заменить ее на закрывающуюсяj+1)</tex>. Таким образом, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобокполучаем формулу:

next(s): pointer_close = 0 pointer_open = 0 for (i = length(s); i <tex> 0; d[i--) if (s][ij] == '('): pointer_open++ if (pointer_close > pointer_open) break else pointer_close++ delete(s, length(s) d[i- pointer_open 1][j- pointer_close + 1, pointer_close ] + l) if (s == ""): return false s = s +')' for (j = d[i-1; j <= pointer_open; ][j++): s = s + '(' for (j = 1; j ]< pointer_close; j++): s = s + ')' return true/tex>

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

===Получение лексикографического порядкаПерейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:===

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

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

Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из <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>.

Здесь пусть $Сложность данного алгоритма <tex>O(n$ — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей^2 + n \cdot k)</tex>.

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

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

$Как и в предыдущем разделе, посчитаем динамику <tex>d[i][j] = d[i-1][j-1] + d[</tex> — количество правильных скобочных последовательностей длины <tex>i-1][</tex> с балансом <tex>j+1]$</tex>.

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

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

$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$.