Поиск k-ой в лексикографическом порядке скобочной последовательности: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
= Решение =
 
= Решение =
−
Будем строить нашу последовательность слева направо, как в [[Поиск k-ой в лексикографическом порядке перестановки|перестановках]]. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(", нам надо ввести вспомогательную функцию $ValidSequencesCount(n, balance)$, где $n ~-$ количество оставшихся позиций в последовательности, а $balance ~-$ текущий скобочный баланс, а сама эта функция возвращает количество ПСП с префиксом, равным тому, который мы уже построили, с оставшейся длиной $n$ и текущим балансом равным $balance$.
+
Будем строить нашу последовательность слева направо, как в [[Поиск k-ой в лексикографическом порядке перестановки|перестановках]]. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(" можно использовать [[Количество ПСП с заданным балансом и нужной длиной
−
 
+
]].
−
= Как считать $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{ставим ")"}}$
 
  
 
{{Автор|Александр Гришутин|rationalex}}
 
{{Автор|Александр Гришутин|rationalex}}
  
 
[[Категория:Конспект]]
 
[[Категория:Конспект]]

Версия 15:01, 6 февраля 2021

Решение

Будем строить нашу последовательность слева направо, как в перестановках. Чтобы узнавать, сколько скобочных последовательностей мы скипнули, поставив ")" вместо "(" можно использовать [[Количество ПСП с заданным балансом и нужной длиной ]].


Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex

Источник — http://wiki.algocode.ru/index.php?title=Поиск_k-ой_в_лексикографическом_порядке_скобочной_последовательности&oldid=1606