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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм проверки правильности скобочной последовательности)
(не показано 39 промежуточных версий 9 участников)
Строка 1: Строка 1:
<wikitex>
 
 
 
== Определения ==
 
== Определения ==
  
 
{{Определение
 
{{Определение
 
|id = def1
 
|id = def1
|definition ='''Скобочная последовательность''' {{---}} класс комбинаторных объектов, представляющих собой последовательность скобочных символов.}}
+
|definition ='''Скобочная последовательность''' (анлг. ''Bracket Sequences'') {{---}} класс комбинаторных объектов, представляющих собой последовательность скобочных символов.}}
'''Примеры скобочных последовательностей:'''
+
'''Примеры скобочных последовательностей'''
*$(())))($
+
*<tex>(())))(</tex>
*$)()()))()(()())$
+
*<tex>)()()))()(()())</tex>
 
{{Определение
 
{{Определение
 
|id = def1
 
|id = def1
|definition ='''Правильная скобочная последовательность''' {{---}} частный случай скобочной последовательности, определяющийся следующими образами:
+
|definition ='''Правильная скобочная последовательность''' (анлг. ''Correct Bracket Sequences'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами:
  
*"" (пустая строка) есть правильная скобочная последовательность;
+
*<tex>\varepsilon</tex> (пустая строка) есть правильная скобочная последовательность;
*пусть $S$ {{---}} правильная скобочная последовательность, тогда $(S)$ есть правильная скобочная последовательность;
+
*пусть <tex>S</tex> {{---}} правильная скобочная последовательность, тогда <tex>(S)</tex> есть правильная скобочная последовательность;
*пусть $S1$, $S2$ {{---}} правильные скобочные последовательности, тогда $S1S2$ есть правильная скобочная последовательность;
+
*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;
 
}}
 
}}
'''Примеры правильных скобочный последовательностей:'''
+
'''Примеры правильных скобочный последовательностей'''
*$((()()()()))$
+
*<tex>((()()()()))</tex>
*$(())(()())$
+
*<tex>(())(()())</tex>
  
 
== Алгоритм проверки правильности скобочной последовательности ==
 
== Алгоритм проверки правильности скобочной последовательности ==
  
Пусть нам дана скобочная последовательность, записанная в строку $s$. Возьмем переменную $pointer$, $pointer = 0$. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем $pointer$ на $1$, закрывающую {{---}} уменьшаем на $1$. Если на протяжении всего перебора $pointer$ было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.
+
Пусть нам дана скобочная последовательность, записанная в строку <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> было неотрицательным (не встречалось закрывающих скобок, для которых не было соответствующих открывающих) и после завершения осталось нулем (все открывающие скобки закрыты, при этом нет лишних закрытых скобок), то скобочная последовательность правильна.
  
===Псевдокод:===
+
===Псевдокод===
  
   check(s):
+
   '''boolean''' check(s: '''string'''):
     pointer = 0
+
     counter = 0
     for (i = 1; i <= length(s); i++):
+
     '''for''' i = 1 '''to''' length(s)
       pointer = (s[i] == '(')? pointer++ : pointer--  
+
       '''if''' s[i] == '('
       if (pointer < 0)
+
        counter++
         return false  
+
      '''else'''
     if (pointer == 0)
+
        counter--  
      return true
+
       '''if''' counter < 0
    else
+
         '''return''' ''false''
      return false
+
     '''return''' counter == 0
  
 
Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
 
Надо отметить, что скобочные последовательности могут состоять не только из одного типа скобок. При этом недопустимо такое расположение, когда один тип скобок закрывает другой:
  
===Примеры скобочных последовательностей с несколькими типами скобок:===
+
===Примеры скобочных последовательностей с несколькими типами скобок===
  
*$()[()]\{()()[]\}$ {{---}} верно
+
*<tex>()[()]\{()()[]\}</tex> {{---}} верно
*$[(]\{\})$ {{---}} неверно
+
*<tex>[(]\{\})</tex> {{---}} неверно
  
В этом случае для проверки надо будет использовать стек.
+
В этом случае для проверки надо будет использовать [[Стек | стек]].
  
== Лексикографический порядок порядок правильных скобочных последовательностей ==
+
== Лексикографический порядок правильных скобочных последовательностей ==
  
Для того чтобы определить лексикографический порядок для правильных скобочных последовательностей надо установить порядок на алфавите, например так '$($' < '$)$'.
+
Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так <tex>(\ <\ )</tex>. Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например <tex>(\ <\ [\ <\ )\ <\ ]</tex>.
Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".
 
  
===Примеры лексикографического порядка для $n$ и $k$, где $n$ {{---}} число открывающихся скобок, а $k$ {{---}} число видов скобок===
+
===Примеры лексикографического порядка для <tex>n</tex> и <tex>k</tex>, где <tex>n</tex> {{---}} число открывающихся скобок, а <tex>k</tex> {{---}} число видов скобок===
  
{| border="1" cellpadding="3"
+
{| class="wikitable"
  |$n = 3$||$k = 1$
+
!colspan="2" style="padding:7px"| <tex>n = 3</tex>
 +
  !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>
 
  |}
 
  |}
  
{| border="1" cellpadding="3"
+
{| class="wikitable" cellpadding="3"
  |$n = 2$||$k = 2$
+
  !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> открывающимися скобками:
  
Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.
+
Для запуска алгоритма необходимо сделать вызов <tex>\mathrm{gen}(n</tex>, <tex>0</tex>, <tex>0</tex>, <tex>"")</tex>.
{{Определение
+
*<tex> \mathtt{ans}</tex> {{---}} строка, в которой мы считаем ответ
|id = def1
+
*<tex> \mathtt{counter\_open}</tex> - количество открывающих скобок в данный момент
|definition =Числа Каталана {{---}} последовательность чисел, выражающих:
+
*<tex> \mathtt{counter\_close}</tex> - количество закрывающих скобок в данный момент
*количество не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями;
+
  '''function''' gen(n: '''int''', counter_open: '''int''', counter_close: '''int''', ans: '''string'''):
*количество способов соединения $2n$ точек на окружности $n$ не пересекающимися хордами;
+
    '''if''' counter_open + counter_close == 2 * n
*количество разбиений выпуклого $(n + 2)$-угольника на треугольники не пересекающимися диагоналями;
+
      print(ans)
*количество способов полностью разделить скобками $n + 1$ множитель;
+
      '''return'''
*количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;}}
+
    '''if''' counter_open < n
===Рекурентная формула:===
+
      gen(n, counter_open + 1, counter_close, ans + '(')
 +
    '''if''' counter_open > counter_close
 +
      gen(n, counter_open, counter_close + 1, ans + ')')
  
$C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i}$
+
Если есть возможность поставить открывающую скобку, то мы ставим её. Аналогично после этого если есть возможность поставить закрывающую скобку, то после этого мы ставим и её.<br>
 +
Таким образом строки будут выведены в лексографическом порядке, так как сначала мы мы пытаемся поставить открывающую скобку.
 +
При этом мы перебираем все возможные варианты последующих скобок для каждого возможного префикса <tex>\mathtt{ans}</tex>, а следовательно в результате получаем все возможножные правильные скобочные последовательности
  
Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.
+
===Генерация следующей скобочной последовательности===
  
Самой левой открывающей скобке $l$ соответствует определённая закрывающая скобка $r$, которая разбивает формулу две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим $i = r - l - 1$, то для любого фиксированного $r$ будет ровно $C_i C_{n-1-i}$ способов. Суммируя это по всем допустимым i, мы и получаем рекуррентную зависимость на $C_n$.
+
Пусть нам известна строка <tex>s</tex>, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то вывести "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить (на этом месте мы можем поставить закрывающую скобку, не нарушив условия правильности скобочной последовательности, то есть на протяжении проверки на правильность counter должен быть неотрицательным), заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
  
===Аналитическая формула:===
+
  '''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
  
$ C_n = \frac{1}{n+1} C_{2n}^{n} $
+
===Получение лексикографического порядка===
  
(здесь через $C_n^k$ обозначен, как обычно, биномиальный коэффициент).
+
Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:
  
Эту формулу проще всего вывести из задачи о монотонных путях. Общее количество монотонных путей в решётке размером $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}$. В результате получаем формулу:
+
  '''function''' order(n: '''int'''):
 +
    s = ""
 +
    '''for''' j = 1 '''to''' n
 +
      s = s + '('
 +
    '''for''' j = 1 '''to''' n
 +
      s = s + ')'
 +
    print(s)
 +
    '''while''' next(s) != "No Solution"
 +
      print(s = next(s))
 +
    '''return'''
  
$ C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{1}{n+1} C_{2n}^{n}$
+
Также с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших <tex>n</tex>.
  
== Алгоритмы генерации ==
+
===Получение номера последовательности===
 +
 
 +
Пусть <tex>n</tex> — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.
  
===Генерация следующей скобочной последовательности:===
+
Научимся считать вспомогательную [[Динамическое программирование | динамику]] <tex>d[i][j]</tex>, где <tex>i</tex> — длина скобочной последовательности (она "полуправильная": всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты), <tex>j</tex> — баланс (т.е. разность между количеством открывающих и закрывающих скобок), <tex>d[i][j]</tex> — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.
  
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
+
Считать эту динамику можно следующим образом. Пусть <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>. Таким образом, получаем формулу:
  
  next(s):
+
<tex>d[i][j] = d[i-1][j-1] + d[i-1][j+1]</tex>
    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".
+
(считается, что все значения <tex>d[i][j]</tex> при отрицательном <tex>j</tex> равны нулю). Таким образом, эту динамику мы можем посчитать за <tex>O(n^2)</tex>.
  
===Получение лексикографического порядка:===
+
Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:
  
Пусть нам известно число $n$. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с $n$ открывающимися скобками:
+
  '''int''' get_number(s: '''string'''):
 +
    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
  
  order (n)
+
Пусть теперь разрешены скобки <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> типов скобок). Утверждается, что формула для этого количества имеет вид:
    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$.
+
<tex>d[2n - i - 1][ndepth] \cdot k^{(2n - i - 1 - ndepth) / 2}</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>.
  
Здесь пусть $n$ — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.
+
Сложность данного алгоритма <tex>O(n^2 + n \cdot k)</tex>.
  
Научимся считать вспомогательную '''динамику''' $d[i][j]$, где $i$ — длина скобочной последовательности (она "полуправильна": всякой закрывающей скобке имеется парная открывающая, но не все открытые скобки закрыты), $j$ — баланс (т.е. разность между количеством открывающих и закрывающих скобок), $d[i][j]$ — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.
+
===Получение k-й последовательности===
  
Считать эту динамику можно следующим образом. Пусть $d[i][j]$ величина, которую мы хотим посчитать. Если $i = 0$, то ответ понятен сразу: $d[0][0] = 1$, все остальные $d[0][j] = 0$. Пусть теперь $i > 0$, тогда мысленно переберём, чему был равен последний символ этой последовательности. Если он был равен '(', то до этого символа мы находились в состоянии $(i-1,j-1)$. Если он был равен ')', то предыдущим было состояние $(i-1,j+1)$. Таким образом, получаем формулу:
+
Пусть <tex>n</tex> количество пар скобок в последовательности. В данной задаче по заданному <tex>k</tex> требуется найти <tex>k</tex>-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.
  
$d[i][j] = d[i-1][j-1] + d[i-1][j+1]$
+
Как и в предыдущем разделе, посчитаем динамику <tex>d[i][j]</tex> — количество правильных скобочных последовательностей длины <tex>i</tex> с балансом <tex>j</tex>.
  
(считается, что все значения $d[i][j]$ при отрицательном $j$ равны нулю). Таким образом, эту динамику мы можем посчитать за $O(n^2)$.
+
Пусть сначала допустимы только скобки одного типа:
  
Перейдём теперь к решению самой задачи.
+
  '''string''' get_sequence(n: '''int''', k: '''int'''):
 +
    depth = 0
 +
    s = ""
 +
    '''for''' i = 0 '''to''' 2 * n - 1
 +
      '''if''' d[2 * n - (i + 1)][depth + 1] <tex>\geqslant</tex> k
 +
        s += '('
 +
        depth++
 +
      '''else'''
 +
        k -= d[2 * n - (i + 1)][depth + 1]
 +
        s += ')'
 +
        depth--
 +
    '''return''' s
  
Сначала пусть допустимы только скобки '''одного''' типа. Заведём счётчик $\rm depth$ глубины вложенности в скобки, и будем двигаться по последовательности слева направо. Если текущий символ $s[i] (i=0 \ldots 2n-1)$ равен '(', то мы увеличиваем $\rm depth$ на $1$ и переходим к следующему символу. Если же текущий символ равен ')', то мы должны прибавить к ответу $d[2n - i - 1][\rm depth + 1]$, тем самым учитывая, что в этой позиции мог бы стоять символ '(' (который бы привёл к лексикографически меньшей последовательности, чем текущая); затем мы уменьшаем $\rm depth$ на единицу.
+
Пусть теперь разрешён не один, а <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> скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).
  
Пусть теперь разрешены скобки '''нескольких''' $k$ типов. Тогда при рассмотрении текущего символа $s[i]$ до пересчёта $\rm depth$ мы должны перебирать все скобки, которые меньше текущего символа, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс $\rm ndepth = \rm depth \pm 1$), и прибавлять к ответу количество соответствующих "хвостов" - завершений (которые имеют длину $2n - i - 1$, баланс $\rm ndepth$ и $k$ типов скобок). Утверждается, что формула для этого количества имеет вид:
+
Сложность данного алгоритма <tex>O(n^2 + n \cdot k)</tex>.
  
$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$.
+
== См. также ==
 +
*[[Числа Каталана]]
 +
*[[Комбинаторные объекты]]
 +
*[[Лексикографический порядок]]
 +
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
 +
*[[Получение номера по объекту]]
 +
*[[Получение объекта по номеру]]
 +
*[[Получение следующего объекта]]
  
 
== Источники ==
 
== Источники ==
Строка 176: Строка 214:
  
 
* [http://e-maxx.ru/algo/bracket_sequences MAXimal :: algo :: Правильные скобочные последовательности]
 
* [http://e-maxx.ru/algo/bracket_sequences MAXimal :: algo :: Правильные скобочные последовательности]
 
* [http://e-maxx.ru/algo/catalan_numbers MAXimal :: algo :: Числа Каталана]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Версия 12:11, 20 мая 2019

Определения

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

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

  • [math](())))([/math]
  • [math])()()))()(()())[/math]
Определение:
Правильная скобочная последовательность (анлг. Correct Bracket Sequences) — частный случай скобочной последовательности, определяющийся следующими образами:
  • [math]\varepsilon[/math] (пустая строка) есть правильная скобочная последовательность;
  • пусть [math]S[/math] — правильная скобочная последовательность, тогда [math](S)[/math] есть правильная скобочная последовательность;
  • пусть [math]S1[/math], [math]S2[/math] — правильные скобочные последовательности, тогда [math]S1S2[/math] есть правильная скобочная последовательность;

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

  • [math]((()()()()))[/math]
  • [math](())(()())[/math]

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

Пусть нам дана скобочная последовательность, записанная в строку [math]s[/math]. Возьмем переменную [math]\mathtt{counter}[/math], [math]\mathtt{counter} = 0[/math], в которой мы будем поддерживать баланс. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем [math]\mathtt{counter}[/math] на [math]1[/math], закрывающую — уменьшаем на [math]1[/math]. Если на протяжении всего перебора [math]\mathtt{counter}[/math] было неотрицательным (не встречалось закрывающих скобок, для которых не было соответствующих открывающих) и после завершения осталось нулем (все открывающие скобки закрыты, при этом нет лишних закрытых скобок), то скобочная последовательность правильна.

Псевдокод

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

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

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

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

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

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

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

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

[math]n = 3[/math] [math]k = 1[/math]
[math]((()))[/math] [math](()())[/math] [math](())()[/math] [math]()(())[/math] [math]()()()[/math]
[math]n = 2[/math] [math]k = 2[/math]
[math]()[][/math] [math]([])[/math] [math][()][/math] [math][]()[/math]

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

Рекурсивный алгоритм получения лексикографического порядка

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

Для запуска алгоритма необходимо сделать вызов [math]\mathrm{gen}(n[/math], [math]0[/math], [math]0[/math], [math]"")[/math].

  • [math] \mathtt{ans}[/math] — строка, в которой мы считаем ответ
  • [math] \mathtt{counter\_open}[/math] - количество открывающих скобок в данный момент
  • [math] \mathtt{counter\_close}[/math] - количество закрывающих скобок в данный момент
 function gen(n: int, counter_open: int, counter_close: int, ans: string):
   if counter_open + counter_close == 2 * n
     print(ans)
     return
   if counter_open < n
     gen(n, counter_open + 1, counter_close, ans + '(')
   if counter_open > counter_close
     gen(n, counter_open, counter_close + 1, ans + ')')

Если есть возможность поставить открывающую скобку, то мы ставим её. Аналогично после этого если есть возможность поставить закрывающую скобку, то после этого мы ставим и её.
Таким образом строки будут выведены в лексографическом порядке, так как сначала мы мы пытаемся поставить открывающую скобку. При этом мы перебираем все возможные варианты последующих скобок для каждого возможного префикса [math]\mathtt{ans}[/math], а следовательно в результате получаем все возможножные правильные скобочные последовательности

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

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

 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++
   // начиная с символа с индексом "length(s) - counter_open - counter_close" удаляем все символы (индексация с 0)
   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

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

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

 function order(n: int):
   s = ""
   for j = 1 to n
     s = s + '('
   for j = 1 to n
     s = s + ')'
   print(s)
   while next(s) != "No Solution"
     print(s = next(s))
   return

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

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

Пусть [math]n[/math] — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.

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

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

[math]d[i][j] = d[i-1][j-1] + d[i-1][j+1][/math]

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

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

 int get_number(s: string):
    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

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

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

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

Сложность данного алгоритма [math]O(n^2 + n \cdot k)[/math].

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

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

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

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

 string get_sequence(n: int, k: int):
   depth = 0
   s = ""
   for i = 0 to 2 * n - 1
     if d[2 * n - (i + 1)][depth + 1] [math]\geqslant[/math] k
       s += '('
       depth++
     else
       k -= d[2 * n - (i + 1)][depth + 1]
       s += ')'
       depth--
   return s

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

Сложность данного алгоритма [math]O(n^2 + n \cdot k)[/math].

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

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

См. также

Источники