Правильные скобочные последовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 20: Строка 20:
 
</wikitex>
 
</wikitex>
 
== Алгоритм проверки правильности скобочной последовательности ==
 
== Алгоритм проверки правильности скобочной последовательности ==
 
+
<wikitex>
 
Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $counter$, $counter = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $counter$ на $1$, закрывающую {{---}} уменьшаем на $1$. Если на протяжении всего перебора $counter$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
 
Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $counter$, $counter = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $counter$ на $1$, закрывающую {{---}} уменьшаем на $1$. Если на протяжении всего перебора $counter$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
 
+
</wikitex>
 
===Псевдокод===
 
===Псевдокод===
 
+
<wikitex>
 
   check(s)
 
   check(s)
 
     counter = 0
 
     counter = 0
Строка 40: Строка 40:
  
 
Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
 
Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
 
+
</wikitex>
 
===Примеры скобочных последовательностей с несколькими типами скобок===
 
===Примеры скобочных последовательностей с несколькими типами скобок===
 
+
<wikitex>
 
*$()[()]\{()()[]\}$ {{---}} верно
 
*$()[()]\{()()[]\}$ {{---}} верно
 
*$[(]\{\})$ {{---}} неверно
 
*$[(]\{\})$ {{---}} неверно
  
 
В этом случае для проверки надо будет использовать стек.
 
В этом случае для проверки надо будет использовать стек.
 
+
</wikitex>
 
== Лексикографический порядок порядок правильных скобочных последовательностей ==
 
== Лексикографический порядок порядок правильных скобочных последовательностей ==
 
+
<wikitex>
 
Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так '$($' < '$)$'.
 
Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так '$($' < '$)$'.
 
Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".
 
Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".
 
+
</wikitex>
 
===Примеры лексикографического порядка для $n$ и $k$, где $n$ {{---}} число открывающихся скобок, а $k$ {{---}} число видов скобок===
 
===Примеры лексикографического порядка для $n$ и $k$, где $n$ {{---}} число открывающихся скобок, а $k$ {{---}} число видов скобок===
 
+
<wikitex>
 
{| border="1" cellpadding="3"
 
{| border="1" cellpadding="3"
 
  |$n = 3$||$k = 1$
 
  |$n = 3$||$k = 1$
Строка 68: Строка 68:
  
 
Алгоритм генерации лексикографического порядка будет предложен ниже.
 
Алгоритм генерации лексикографического порядка будет предложен ниже.
 
+
</wikitex>
 
== Количество правильных скобочных последовательностей. Числа Каталана ==
 
== Количество правильных скобочных последовательностей. Числа Каталана ==
 
+
<wikitex>
 
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.
 
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.
 
{{Определение
 
{{Определение
Строка 80: Строка 80:
 
*количество способов полностью разделить скобками $n + 1$ множитель;
 
*количество способов полностью разделить скобками $n + 1$ множитель;
 
*количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;}}
 
*количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;}}
 +
</wikitex>
 
===Рекурентная формула===
 
===Рекурентная формула===
 
+
<wikitex>
 
$C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}$
 
$C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}$
  
Строка 87: Строка 88:
  
 
Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $i = r - l - 1$, то для любого фиксированного $r$ будет ровно $C_i C_{n-1-i}$ способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на $C_n$.
 
Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $i = r - l - 1$, то для любого фиксированного $r$ будет ровно $C_i C_{n-1-i}$ способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на $C_n$.
 
+
</wikitex>
 
===Аналитическая формула===
 
===Аналитическая формула===
 
+
<wikitex>
 
$ C_n = \frac{1}{n+1} C_{2n}^{n} $
 
$ C_n = \frac{1}{n+1} C_{2n}^{n} $
  
Строка 97: Строка 98:
  
 
$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$
 
$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$
 
+
</wikitex>
 
== Алгоритмы генерации ==
 
== Алгоритмы генерации ==
 
+
<wikitex>
 
===Генерация следующей скобочной последовательности===
 
===Генерация следующей скобочной последовательности===
 
+
<wikitex>
 
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить, заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
 
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить, заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
  
Строка 125: Строка 126:
  
 
Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".
 
Если эта функция после выполнения выводит $true$, тогда надо напечатать полученную строку $s$, если $false$, то следует вывести "No solution".
 
+
</wikitex>
 
===Получение лексикографического порядка===
 
===Получение лексикографического порядка===
 
+
<wikitex>
 
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:
 
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:
  
Строка 147: Строка 148:
  
 
Также с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $n$.
 
Также с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших $n$.
 
+
</wikitex>
 
===Получение номера последовательности===
 
===Получение номера последовательности===
 
+
<wikitex>
 
Пусть $n$ — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.
 
Пусть $n$ — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.
  
Строка 180: Строка 181:
  
 
Сложность данного алгоритма $O(n^2 + n \cdot k)$.
 
Сложность данного алгоритма $O(n^2 + n \cdot k)$.
 
+
</wikitex>
 
===Получение k-й последовательности===
 
===Получение k-й последовательности===
 
+
<wikitex>
 
Пусть $n$ — количество пар скобок в последовательности. В данной задаче по заданному $k$ требуется найти $k$-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.
 
Пусть $n$ — количество пар скобок в последовательности. В данной задаче по заданному $k$ требуется найти $k$-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.
  
Строка 193: Строка 194:
 
     s = ""
 
     s = ""
 
     for i = 0 to 2 * n - 1
 
     for i = 0 to 2 * n - 1
       if d[i + 1][depth + 1] >= k
+
       if d[2 * n - (i + 1)][2 * n - (depth + 1)] >= k
 
         s += '('
 
         s += '('
 
         depth++
 
         depth++
 
       else
 
       else
         k -= d[i + 1][depth + 1]
+
         k -= d[2 * n - (i + 1)][2 * n - (depth + 1)]
 
         s += ')'
 
         s += ')'
 
         depth--
 
         depth--
Строка 205: Строка 206:
  
 
Сложность данного алгоритма $O(n^2 + n \cdot k)$.  
 
Сложность данного алгоритма $O(n^2 + n \cdot k)$.  
 
+
</wikitex>
 
== Источники ==
 
== Источники ==
 
+
<wikitex>
 
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Скобочные последовательности, Материал из Википедии — свободной энциклопедии]
 
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Скобочные последовательности, Материал из Википедии — свободной энциклопедии]
  
Строка 219: Строка 220:
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]
 +
</wikitex>

Версия 19:26, 19 декабря 2013

Определения

<wikitex>

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

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

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

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

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

</wikitex>

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

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

Псевдокод

<wikitex>

 check(s)
   counter = 0
   for i = 1 to length(s)
     if s[i] == '('
       counter++
     else
       counter-- 
     if counter < 0
       return false 
   if counter == 0
     return true
   else
     return false

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

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

<wikitex>

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

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

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

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

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

<wikitex>

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

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

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

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

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

</wikitex>

Рекурентная формула

<wikitex> $C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}$

Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.

Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $i = r - l - 1$, то для любого фиксированного $r$ будет ровно $C_i C_{n-1-i}$ способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на $C_n$. </wikitex>

Аналитическая формула

<wikitex> $ C_n = \frac{1}{n+1} C_{2n}^{n} $

(здесь через $C_n^k$ обозначен, как обычно, биномиальный коэффициент).

Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $n \times n$ равно $C_{2n}^{n}$. Теперь посчитаем количество монотонных путей, пересекающих диагональ. Рассмотрим какой-либо из таких путей, и найдём первое ребро, которое стоит выше диагонали. Отразим относительно диагонали весь путь, идущий после этого ребра. В результате получим монотонный путь в решётке $(n - 1) \times (n + 1)$. Но, с другой стороны, любой монотонный путь в решётке $(n - 1) \times (n + 1)$ обязательно пересекает диагональ, следовательно, он получен как раз таким способом из какого-либо (причём единственного) монотонного пути, пересекающего диагональ, в решётке $n \times n$. Монотонных путей в решётке $(n - 1) \times (n + 1)$ имеется $C_{2n}^{n-1}$. В результате получаем формулу:

$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$ </wikitex>

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

<wikitex>

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

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

 next(s)
   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++
   delete(s, length(s) - counter_open - counter_close + 1, counter_close + l)
   if s == ""
     return false
   s = s +')'
   for j = 1 to counter_open
     s = s + '('
   for j = 1 to counter_close - 1
     s = s + ')'
   return true

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

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

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

 order(n)
   s = ""
   if n == 0
     result(s)  
   else
     for j = 1 to n
       s = s + '('
     for j = 1 to n
       s = s + ')'
     result(s)
     t = next(s)
     while t != false
       result(s)
       t = next(s)
   return

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

Получение номера последовательности

<wikitex> Пусть $n$ — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.

Научимся считать вспомогательную динамику $d[i][j]$, где $i$ — длина скобочной последовательности (она "полуправильная": всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты), $j$ — баланс (т.е. разность между количеством открывающих и закрывающих скобок), $d[i][j]$ — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.

Считать эту динамику можно следующим образом. Пусть $d[i][j]$ — величина, которую мы хотим посчитать. Если $i = 0$, то ответ понятен сразу: $d[0][0] = 1$, все остальные $d[0][j] = 0$. Пусть теперь $i > 0$, тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен '(', то до этого символа мы находились в состоянии $(i-1,j-1)$. Если он был равен ')', то предыдущим было состояние $(i-1,j+1)$. Таким образом, получаем формулу:

$d[i][j] = d[i-1][j-1] + d[i-1][j+1]$

(считается, что все значения $d[i][j]$ при отрицательном $j$ равны нулю). Таким образом, эту динамику мы можем посчитать за $O(n^2)$.

Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:

 getNumber(s)
    num = 0
    depth = 0
    for i = 0 to 2 * n - 1
      if s[i] == '('
        depth++
      else
        num += d[2 * n - i - 1][depth + 1]
        depth--
    return num

Пусть теперь разрешены скобки $k$ типов. Тогда при рассмотрении текущего символа $s[i]$ до пересчёта $\rm depth$ мы должны перебирать все скобки, которые меньше текущего символа в установленном ранее порядке, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс $\rm ndepth = \rm depth \pm 1$), и прибавлять к ответу количество соответствующих "хвостов" - завершений (которые имеют длину $2n - i - 1$, баланс $\rm ndepth$ и $k$ типов скобок). Утверждается, что формула для этого количества имеет вид:

$d[2n - i - 1][ndepth] \cdot k^{(2n - i - 1 - ndepth) / 2}$

Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из $d[2n - i - 1][{\rm ndepth}]$. Теперь посчитаем, как изменится ответ из-за наличия $k$ типов скобок. У нас имеется $2n - i - 1$ неопределённых позиций, из которых $\rm ndepth$ являются скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет $(2n - i - 1 - {\rm ndepth}) / 2$ пар) могут быть любого из $k$ типов, поэтому ответ умножается на эту степень числа $k$.

Сложность данного алгоритма $O(n^2 + n \cdot k)$. </wikitex>

Получение k-й последовательности

<wikitex> Пусть $n$ — количество пар скобок в последовательности. В данной задаче по заданному $k$ требуется найти $k$-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.

Как и в предыдущем разделе, посчитаем динамику $d[i][j]$ — количество правильных скобочных последовательностей длины $i$ с балансом $j$.

Пусть сначала допустимы только скобки одного типа:

 getSequence(n, k)
   depth = 0
   s = ""
   for i = 0 to 2 * n - 1
     if d[2 * n - (i + 1)][2 * n - (depth + 1)] >= k
       s += '('
       depth++
     else
       k -= d[2 * n - (i + 1)][2 * n - (depth + 1)]
       s += ')'
       depth--
   return s

Пусть теперь разрешён не один, а $k$ типов скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение $d[i + 1][\rm ndepth]$ на величину $k^{(2n - i - 1 - \rm ndepth) / 2}$, чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только $2n - i - 1 - \rm ndepth$, поскольку $\rm ndepth$ скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).

Сложность данного алгоритма $O(n^2 + n \cdot k)$. </wikitex>

Источники

<wikitex>

</wikitex>