Изменения
→Алгоритм проверки правильности скобочной последовательности
|definition ='''Правильная скобочная последовательность''' (анлг. ''Correct Bracket Sequences'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами:
*<tex>\varepsilon</tex> ("", пустая строка) есть правильная скобочная последовательность;
*пусть <tex>S</tex> {{---}} правильная скобочная последовательность, тогда <tex>(S)</tex> есть правильная скобочная последовательность;
*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;
== Алгоритм проверки правильности скобочной последовательности ==
Пусть нам дана скобочная последовательность, записанная в строку <tex>s</tex>. Возьмем переменную <tex>\mathtt{counter}</tex>, <tex>\mathtt{counter } = 0</tex>, в которой мы будем поддерживать баланс. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем <tex>\mathtt{counter}</tex> на <tex>1</tex>, закрывающую {{---}} уменьшаем на <tex>1</tex>. Если на протяжении всего перебора <tex>\mathtt{counter}</tex> было неотрицательным (не встречалось закрывающих скобок, для которых не было соответствующих открывающих) и после завершения осталось нулем (все открывающие скобки закрыты, при этом нету нет лишних закрытых скобок), то скобочная последовательность правильна.
===Псевдокод===
'''boolean''' check(s: '''string'''):
counter = 0
'''for''' i = 1 '''to''' length(s)
В этом случае для проверки надо будет использовать [[Стек | стек]].
== Лексикографический порядок порядок правильных скобочных последовательностей ==
Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так <tex>(\ <\ )</tex>. Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например <tex>(\ <\ [\ <\ )\ <\ ]</tex>.
Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:
Для запуска алгоритма необходимо сделать вызов <tex>\mathrm{gen}</tex>(<tex>n</tex>, <tex>0</tex>, <tex>0</tex>, <tex>\varepsilon"")</tex>).
*<tex> \mathtt{ans}</tex> {{---}} строка, в которой мы считаем ответ
*''counter_open'' <tex> \mathtt{counter\_open}</tex> - количество открывающих скобок в данный момент*''counter_open'' <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>s</tex>, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то вывести "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить (на этом месте мы можем поставить закрывающую скобку, не нарушив условия правильности скобочной последовательности, то есть на протяжении проверки на правильность counter должен быть неотрицательным), заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
'''string''' next(s: '''string'''):
counter_close = 0
counter_open = 0
counter_open++
'''if''' counter_close > counter_open
'''break'''
'''else'''
counter_close++
'''return''' "No Solution"
'''else'''
'''for''' j = 1 '''to''' counter_close - 1
s = s + ')'
'''return''' s;
===Получение лексикографического порядка===
Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:
'''function''' order(n: '''int'''): s = <tex>\varepsilon</tex>""
'''for''' j = 1 '''to''' n
s = s + '('
Научимся считать вспомогательную [[Динамическое программирование | динамику]] <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>
Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:
'''int''' get_number(s: '''string'''):
num = 0
depth = 0
<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 = d depth + 1</tex>, если мы пробуем поставить открывающую скобку, и <tex>d 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>.
Пусть сначала допустимы только скобки одного типа:
'''string''' get_sequence(n: '''int''', k: '''int'''):
depth = 0
s = <tex>\varepsilon</tex>""
'''for''' i = 0 '''to''' 2 * n - 1
'''if''' d[2 * n - (i + 1)][depth + 1] <tex>\geqslant</tex> k
Пусть теперь разрешён не один, а <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>.
==Количество правильных скобочных последовательностей==
