1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|id = def1
|definition ='''Скобочная последовательность''' (анлгангл. ''Bracket Sequences'') {{---}} класс комбинаторных объектов, представляющих собой последовательность скобочных символов.}}
'''Примеры скобочных последовательностей'''
*<tex>(())))(</tex>
*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;
}}
'''Примеры правильных скобочный скобочных последовательностей'''
*<tex>((()()()()))</tex>
*<tex>(())(()())</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> \mathtt{ans}</tex> {{---}} строка, в которой мы считаем ответ
*<tex> \mathtt{counter\_open}</tex> - количество открывающих скобок в данный момент
*<tex> \mathtt{counter\_open_close}</tex> - количество закрывающих скобок в данный момент
'''function''' gen(n: '''int''', counter_open: '''int''', counter_close: '''int''', ans: '''string'''):
'''if''' counter_open + counter_close == 2 * n
Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:
'''function''' order(n: '''int'''):
s = ""
'''for''' j = 1 '''to''' n
Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:
'''int''' get_number(s: '''string'''):
num = 0
depth = 0
Пусть сначала допустимы только скобки одного типа:
'''string''' get_sequence(n: '''int''', k: '''int'''):
depth = 0
s = ""
'''return''' s
Пусть теперь разрешён не один, а <tex>k</tex> типов скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение <tex>d[2n - 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>.
==Количество правильных скобочных последовательностей==
