Изменения

|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$ обозначен, как обычно, биномиальный коэффициент). Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $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$, представляющая собой правильную скобочную последовательностьизвестно число <tex>n</tex>. Нам необходимо Надо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся все правильные скобочные последовательности в конце скобки (если они есть) заменить на минимально возможную последовательность скобоклексикографическом порядке с <tex>n</tex> открывающимися скобками:

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

return trueprint(s)Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $ '''while''' next(s$, если $false$, то следует вывести ) != "No solutionSolution". print(s = next(s))===Получение лексикографического порядка=== '''return'''

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

Здесь пусть $Пусть <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>'('</tex>, то до этого символа мы находились в состоянии $<tex>(i-1,j-1)$</tex>. Если он был равен <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>.

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

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

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

'''else''' num += d[2n 2 * n - i - 1][depth + 1]

'''return ''' num

Пусть теперь разрешены скобки '''нескольких''' $<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>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>.

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

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

Пусть сначала допустимы только скобки '''одного''' типа.:

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

Пусть теперь разрешён не один, а '''$<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>. ==Количество правильных скобочных последовательностей==Количество правильных скобочных последовательностей со скобками одного типа совпадает с [[Числа Каталана | числами Каталана]]. == См. также ==*[[Числа Каталана]]*[[Комбинаторные объекты]]*[[Лексикографический порядок]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение номера по объекту]]*[[Получение объекта по номеру]]*[[Получение следующего объекта]]