Изменения
→Алгоритм проверки правильности скобочной последовательности
== Определения ==
{{Определение
|id = def1
|definition ='''Скобочная последовательность''' (анлг. ''Bracket Sequences'') {{---}} класс комбинаторных объектов, представляющих собой последовательность скобочных символов.}}
'''Примеры скобочных последовательностей'''
*$<tex>(())))($</tex>*$<tex>)()()))()(()())$</tex>
{{Определение
|id = def1
|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> открывающимися скобками:
'''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
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательностьизвестно число <tex>n</tex>. Нам необходимо Надо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся все правильные скобочные последовательности в конце скобки (если они есть) заменить на минимально возможную последовательность скобоклексикографическом порядке с <tex>n</tex> открывающимися скобками:
s = s + '('
'''for (''' j = 1; j < pointer_close; j++):'''to''' n
s = s + ')'
Также с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $<tex>n$</tex>.
===Получение номера последовательности===
Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки '''одного''' типа. Заведём счётчик $\rm depth$ глубины вложенности в скобки, и будем двигаться по последовательности слева направо. Если текущий символ $s[i] (i=0 \ldots 2n-1)$ равен '(', то мы увеличиваем $\rm depth$ на $1$ и переходим к следующему символу. Если же текущий символ равен ')', то мы должны прибавить к ответу $d[2n - i - 1][\rm depth + 1]$, тем самым учитывая, что в этой позиции мог бы стоять символ '(' (который бы привёл к лексикографически меньшей последовательности, чем текущая); затем мы уменьшаем $\rm depth$ на единицу.:
num = 0
depth = 0
'''for (''' i = 0; i < length(s); i++)'''to''' 2 * n - 1 '''if ''' s[i] == '('
depth++
'''else''' num += d[length(s) 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> типов скобок). Утверждается, что формула для этого количества имеет вид:
Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из $<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>.
===Получение 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> скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).
== Источники ==
* [http://e-maxx.ru/algo/bracket_sequences MAXimal :: algo :: Правильные скобочные последовательности]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]