Поиск k-ой в лексикографическом порядке скобочной последовательности: различия между версиями
Материал из Algocode wiki
(Новая страница: «= Решение = Будем строить нашу последовательность слева направо, как в Поиск k-ой в лекси...») |
|||
| Строка 1: | Строка 1: | ||
= Решение = | = Решение = | ||
| − | Будем строить нашу последовательность слева направо, как в [[Поиск k-ой в лексикографическом порядке перестановки|перестановках]]. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ) вместо (, нам надо ввести вспомогательную функцию $ValidSequencesCount(n, balance)$, где $n ~-$ количество оставшихся позиций в последовательности, а $balance ~-$ текущий скобочный баланс, а сама эта функция возвращает количество ПСП с префиксом, равным тому, который мы уже построили, с оставшейся длиной $n$ и текущим балансом равным $balance$. | + | Будем строить нашу последовательность слева направо, как в [[Поиск k-ой в лексикографическом порядке перестановки|перестановках]]. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(", нам надо ввести вспомогательную функцию $ValidSequencesCount(n, balance)$, где $n ~-$ количество оставшихся позиций в последовательности, а $balance ~-$ текущий скобочный баланс, а сама эта функция возвращает количество ПСП с префиксом, равным тому, который мы уже построили, с оставшейся длиной $n$ и текущим балансом равным $balance$. |
= Как считать $ValidSequencesCount$ ? = | = Как считать $ValidSequencesCount$ ? = | ||
Версия 11:52, 22 февраля 2020
Решение
Будем строить нашу последовательность слева направо, как в перестановках. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(", нам надо ввести вспомогательную функцию $ValidSequencesCount(n, balance)$, где $n ~-$ количество оставшихся позиций в последовательности, а $balance ~-$ текущий скобочный баланс, а сама эта функция возвращает количество ПСП с префиксом, равным тому, который мы уже построили, с оставшейся длиной $n$ и текущим балансом равным $balance$.
Как считать $ValidSequencesCount$ ?
Предподсчитаем все значения этой функции динамическим программированием.
- База $VSC[0][0] = 1$, $VSC[0][1 \ldots n] = 0$
- Переход $VSC[n][balance] = \underbrace{VSC[n-1][balance + 1]}_{\text{ставим (}} + \underbrace{VSC[n-1][balance - 1]}_{\text{ставим )}}$
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex