Правильные скобочные последовательности

<wikitex>

Определения

Определение:

Скобочная последовательность — класс комбинаторных объектов, представляющих собой последовательность скобочных символов.

Примеры скобочных последовательностей:

• $(())))($
• $)()()))()(()())$

Определение:

Правильная скобочная последовательность — частный случай скобочной последовательности, определяющийся следующими образами: "" (пустая строка) есть правильная скобочная последовательность; пусть $S$ — правильная скобочная последовательность, тогда $(S)$ есть правильная скобочная последовательность; пусть $S1$, $S2$ — правильные скобочные последовательности, тогда $S1S2$ есть правильная скобочная последовательность;

Примеры правильных скобочный последовательностей:

• $((()()()()))$
• $(())(()())$

Алгоритм проверки правильности скобочной последовательности

Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $pointer$, $pointer = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $pointer$ на $1$, закрывающую — уменьшаем на $1$. Если на протяжении всего перебора $pointer$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.

псевдокод:

 check(s):
   pointer = 0
   for (i = 1; i <= length(s); i++):
     pointer = (s[i] == '(')? pointer++ : pointer-- 
     if (pointer < 0)
       return false 
   if (pointer == 0)
     return true
   else
     return false

Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:

Примеры скобочных последовательностей с несколькими типами скобок:

• $()[()]\{()()[]\}$ — верно
• $[(]\{\})$ — неверно

В этом случае для проверки надо будет использовать стек.

Лексикографический порядок порядок правильных скобочных последовательностей

Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей надо установить порядок на алфавите, например так '$($' < '$)$'. Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".

Примеры лексикографического порядка для $n$ и $k$, где $n$ — число открывающихся скобок, а $k$ — число видов скобок

$n = 3$	$k = 1$
$((()))$	$(()())$	$(())()$	$()(())$	$()()()$

$n = 2$	$k = 2$
$()[]$	$([])$	$[()]$	$[]()$

Алгоритм генерации лексикографического порядка будет предложен ниже.

Количество правильных скобочных последовательностей. Числа Каталана

Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.

Определение:

Числа Каталана — последовательность чисел, выражающих: количество не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями; количество способов соединения $2n$ точек на окружности $n$ не пересекающимися хордами; количество разбиений выпуклого $(n + 2)$-угольника на треугольники не пересекающимися диагоналями;

Для чисел Каталана выполняется выражение:

$C_n =\frac{(2n)!}{n!(n + 1)!}$,

а также они удовлетворяют рекуррентному соотношению:

$C_0 = 1$ — так как существует только одна скобочная последовательность с $0$ открывающихся скобок — пустая

$C_n = \sum_{i = 1}^{n - 1} C_i C_{n - 1 - i}$.

Чтобы получить это соотношение, надо перебрать все возможные последовательности $S1$ и $S2$, являющиеся правильными скобочными последовательностями, такие, что $(S1)S2$ образуют новые правильные скобочные последовательности необходимой нам длины.

Алгоритмы генерации

Генерация следующей скобочной последовательности:

Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то — "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:

 next(s): 
   pointer_close = 0
   pointer_open = 0
   for (i = length(s); i > 0; i--)
       if (s[i] == '('):
         pointer_open++ 
         if (pointer_close > pointer_open)
           break
       else 
         pointer_close++
   delete(s, length(s) - pointer_open - pointer_close + 1, pointer_close + l)
   if (s == ""):
     return false
   s = s +')'
   for (j = 1; j <= pointer_open; j++):
     s = s + '('
   for (j = 1; j < pointer_close; j++):
     s = s + ')'
   return true

Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".

Получение лексикографического порядка:

Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:

 order (n)
   s = "";
   if (n == 0):
     result(s)  
   else
     for (j = 1; j <= n; i++)
       s = s + '(';
     for (j = 1; j <= n; i++)
       s = s + ')';
     result(s);
     t = next(s);
     while (t <> false)
       result(s);
       t = next(s);
   return

Так же с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $n$.