55
правок
Изменения
Нет описания правки
|definition ='''Правильная скобочная последовательность''' (анлг. ''Correct Bracket Sequences'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами:
*<tex>\varepsilon</tex> ("", пустая строка) есть правильная скобочная последовательность;
*пусть <tex>S</tex> {{---}} правильная скобочная последовательность, тогда <tex>(S)</tex> есть правильная скобочная последовательность;
*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;
Пусть нам известно число <tex>n</tex>. Надо вывести все правильные скобочные последовательности в лексикографическом порядке с <tex>n</tex> открывающимися скобками:
Для запуска алгоритма необходимо сделать вызов <tex>\mathrm{gen}</tex>(<tex>n</tex>, <tex>0</tex>, <tex>0</tex>, <tex>\varepsilon"")</tex>).
*<tex> \mathtt{ans}</tex> {{---}} строка, в которой мы считаем ответ
*''<tex> \mathtt{counter_open'' }</tex> - количество открывающих скобок в данный момент*''<tex> \mathtt{counter_open'' }</tex> - количество закрывающих скобок в данный момент '''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 + "')"')
Если есть возможность поставить открывающую скобку, то мы ставим её. Аналогично после этого если есть возможность поставить закрывающую скобку, то после этого мы ставим и её.<br>
Таким образом строки будут выведены в лексографическом порядке, так как сначала мы мы пытаемся поставить открывающую скобку.
===Генерация следующей скобочной последовательности===
counter_open++
'''if''' counter_close > counter_open
'''break'''
'''else'''
counter_close++
delete(s, length(s) - counter_open - counter_close + 1, counter_close + lcounter_open) <span style="color:Green">// начиная с символа с индексом "length(s) - counter_open - counter_close" удаляем все символы (индексация с 0)</span> '''if''' s == <tex>\varepsilon</tex>""
'''return''' "No Solution"
'''else'''
'''for''' j = 1 '''to''' counter_close - 1
s = s + ')'
'''return''' s;
===Получение лексикографического порядка===
'''function''' order(n: '''int''')
s = <tex>\varepsilon</tex>""
'''for''' j = 1 '''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] = d[i-1][j-1] + d[i-1][j+1]</tex>
<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 = d depth + 1</tex>, если мы пробуем поставить открывающую скобку, и <tex>d 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>.
'''string''' get_sequence(n: '''int''', k: '''int''')
depth = 0
s = <tex>\varepsilon</tex>""
'''for''' i = 0 '''to''' 2 * n - 1
'''if''' d[2 * n - (i + 1)][depth + 1] <tex>\geqslant</tex> k
