Изменения
→Алгоритм проверки правильности скобочной последовательности
== Определения ==
{{Определение
|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>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]$ </tex> при отрицательном $<tex>j$ </tex> равны нулю). Таким образом, эту динамику мы можем посчитать за $<tex>O(n^2)$</tex>.
Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки '''одного''' типа.:
num = 0
depth = 0
'''for (''' i = 0; i < 2n; i++)'''to''' 2 * n - 1 '''if ''' s[i] == '('
depth++
'''else''' num += d[2n 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>d[i][j]$ </tex> — количество правильных скобочных последовательностей длины $<tex>i$ </tex> с балансом $<tex>j$</tex>.
Пусть сначала допустимы только скобки '''одного''' типа.:
Пусть теперь разрешён не один, а '''$<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>. ==Количество правильных скобочных последовательностей==Количество правильных скобочных последовательностей со скобками одного типа совпадает с [[Числа Каталана | числами Каталана]]. == См. также ==*[[Числа Каталана]]*[[Комбинаторные объекты]]*[[Лексикографический порядок]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение номера по объекту]]*[[Получение объекта по номеру]]*[[Получение следующего объекта]]
== Источники ==
* [http://e-maxx.ru/algo/bracket_sequences MAXimal :: algo :: Правильные скобочные последовательности]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]