Генерация объекта по номеру

Материал из Algocode wiki
Перейти к: навигация, поиск

Допустим, нам нужно получить $k$-й объект в лексикографическом порядке (перестановку, сочетание, скобочную последовательность итд). Рассмотрим, к примеру, нахождение $k$-й правильной скобочной последовательности.

Будем решать рекурсивно. Пусть нам пришел текущий префикс $s$, баланс $b$ и число $k$ - номер искомой последовательности. Нам нужно понять, какую скобку сейчас поставить. Понятно, что лексикографически сначала идут последовательности с префиксом $s + '('$, а затем $s + ')'$. Пусть количество последовательностей начинающихся на $s + '('$ у нас $c_1$, а на $s + ')'$ - $c_2$. Тогда, если $k \leq c_1$, нужный нам префикс $s + '('$. Иначе вычтем $c_1$ из $k$ (чтобы в дальнейшем не учитывать уже рассмотренные последовательности), припишем к $s$ закрывающую скобку. А затем запускаемся рекурсивно.

Аналогичная идея работает и для прочих объектов: мы просто смотрим на все варианты продолжения нашего префикса, идём по ним лексикографически, вычитая из $k$ количество объектов, начинающихся на соответствующий префикс, если $k$ больше этого количества, и продлеваем префикс минимальным объектом, на котором $k$ стало не превышать это количество.



Автор конспекта: Егор Гутров

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