Изменения

|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{ans}</tex> {{---}} строка, в которой мы считаем ответ*<tex> \mathtt{counter\_open}</tex> - количество открывающих скобок в данный момент*<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, counter_close, ans + '(') '''if''' counter_open > counter_close gen(n, counter_open, counter_close + 1, ans + ')') Если есть возможность поставить открывающую скобку, то мы ставим её. Аналогично после этого если есть возможность поставить закрывающую скобку, то после этого мы ставим и её.<br>Таким образом строки будут выведены в лексографическом порядке, так как сначала мы мы пытаемся поставить открывающую скобку. При этом мы перебираем все возможные варианты последующих скобок для каждого возможного префикса <tex>\mathtt{ans}</tex>, а следовательно в результате получаем все возможножные правильные скобочные последовательности ===Генерация следующей скобочной последовательности=== Пусть нам известна строка <tex>s</tex>, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то вывести "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить (на этом месте мы можем поставить закрывающую скобку, не нарушив условия правильности скобочной последовательности, то есть на протяжении проверки на правильность 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 ===Получение лексикографического порядка=== Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:  '''function''' order(n: '''int'''): s = "" '''for''' j = 1 '''to''' n s = s + '(' '''for''' j = 1 '''to''' n s = s + ')' print(s) '''while''' next(s) != "No Solution" print(s = 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>. Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:  '''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 Пусть теперь разрешены скобки <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> типов скобок).Утверждается, что формула для этого количества имеет вид:

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

$C_n =\frac{Сложность данного алгоритма <tex>O(2n)!}{n!(^2 + n + 1\cdot k)!}$,</tex>.

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

$C_n = \sum_{Как и в предыдущем разделе, посчитаем динамику <tex>d[i = 1}^{n - 1} C_i C_{n - 1 - ][j]</tex> — количество правильных скобочных последовательностей длины <tex>i}$</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

Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки Сложность данного алгоритма <tex>O(если они естьn^2 + n \cdot k) заменить на минимально возможную последовательность скобок:</tex>.

next(s): pointer_close = 0 pointer_open = 0 for (i Количество правильных скобочных последовательностей== length(s); i > 0; i--) if (sКоличество правильных скобочных последовательностей со скобками одного типа совпадает с [[iЧисла Каталана | числами Каталана]] == '('): 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++): s = s + '(' for (j = 1; j < pointer_close; j++): s = s + ')' return true.

Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution"== См.также ==*[[Числа Каталана]]*[[Комбинаторные объекты]]*[[Лексикографический порядок]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение номера по объекту]]*[[Получение объекта по номеру]]*[[Получение следующего объекта]]

Пусть нам известно число $n$* [http://ru. Надо вывести все правильные скобочные wikipedia.org/wiki/%D0%A1%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:, Материал из Википедии — свободной энциклопедии]

order (n) s = ""; if (n == 0)* [http: 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//ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Правильная скобочная последовательность, Материал из Википедии — свободной энциклопедии]

Так же с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной * [http://e-maxx.ru/algo/bracket_sequences MAXimal :: algo :: Правильные скобочные последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $n$.]