74
правки
Изменения
→Правильные скобочные последовательности
Рассмотрим "полуправильные" скобочные последовательности т.е. такие что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты. Такую последовтеьность можно охарактеризовать двумя числами: <tex> l </tex> — длина скобочной последовательности и <tex> b </tex> — баланс (т.е. разность между количеством открывающих и закрывающих скобок). Заметим что любой префикс правильной скобочной последовательности является "полупраильной" скобочной последовательностью, и что для любого префикса <tex> P </tex> длины <tex> l </tex> число различных ПСП длины <tex> n </tex> равно числу "полуправильных" скобочных последовательностей длины <tex> n-l </tex> с таким же балансом как у <tex> P </tex>.
Научимся считать <tex> numberD(l, b) </tex> {{---}} число последовательностей длины <tex> l </tex> и баланса <tex> b </tex>). Если <tex> l = 0 </tex>, то ответ понятен сразу: <tex> numberD[0][0] = 1 </tex>, все остальные <tex> numberD[0][b] = 0 </tex>. Пусть теперь <tex> i l > 0 </tex>, тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен <tex> '(' </tex>, то до этого символа мы находились в состоянии <tex> (l-1,b-1) </tex>. Если он был равен <tex>')'</tex>, то предыдущим было состояние <tex>(l-1,b+1)</tex>. Таким образом, получаем формулу:
<tex>numberD[l][b] = numberD[l-1][b-1] + numberD[l-1][b+1]</tex>
(считается, что все значения <tex> numberD[l][b] </tex> при отрицательном <tex>j</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</tex>.
Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (где <tex> s = numberD[n - l][b] </tex>) , будет разбиваться на два диапазона размерами <tex> numberD[n - l - 1][b + 1] </tex> и <tex> numberD[n - l - 1][b - 1] </tex> , и к префиксу будет прибавляться <tex>'('</tex> или <tex>')'</tex> если случайное число попало в первый или второй диапазон соответственно.
'''string''' randomBracketSequence(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font>
l = 0
'''for''' i = 1 '''to''' n
s = numberD[n - l][b]
r = random(1, s)
'''if''' numberD[n - l - 1][b + 1] >= r
l = l + 1
b = b + 1
