Изменения
Нет описания правки
check(s):
for (i = 1; i <= length(s); i++):
return false
if (pointer counter == 0)
return true
else
== Лексикографический порядок порядок правильных скобочных последовательностей ==
Для того , чтобы определить лексикографический порядок для правильных скобочных последовательностей , надо установить порядок на алфавите, например так '$($' < '$)$'.
Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например "$($" < "$[$" < "$)$" < "$]$".
===Генерация следующей скобочной последовательности===
Пусть нам известна строка $s$, представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то {{---}} "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:
next(s):
Пусть $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]$ при отрицательном $j$ равны нулю). Таким образом, эту динамику мы можем посчитать за $O(n^2)$.
Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки '''одного''' типа.:
getNumber(s)
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}$
Пусть $n$ — количество пар скобок в последовательности. В данной задаче по заданному $k$ требуется найти $k$-ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.
Как и в предыдущем разделе, посчитаем '''динамику''' $d[i][j]$ — количество правильных скобочных последовательностей длины $i$ с балансом $j$.
Пусть сначала допустимы только скобки '''одного''' типа.:
getSequence(n, k)
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)$.
