Изменения
→Алгоритм проверки правильности скобочной последовательности
== Алгоритм проверки правильности скобочной последовательности ==
Пусть нам дана скобочная последовательность, записанная в строку <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
Пусть сначала допустимы только скобки одного типа:
'''string''' get_sequence(n: '''int''', k: '''int'''):
depth = 0
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>.
==Количество правильных скобочных последовательностей==
