Генерация комбинаторных объектов

Недавно была тема восстановление $k$-ого комбинаторного объекта и там для восстановление сложных объектов мы использовали динамику, значит восстановление $k$-ого числа наверное тоже можно делать через динамику, например пусть дана задача найти $k$ число с суммой цифр = $s$, первым делом нам надо найти длину такого числа, то есть найти $min(x), dp[x][s] >= k$, теперь нам нужно восстановить само число, для этого давайте переберем первую цифру от 1 до 9, найдем минимальную для которой возможно, затем переберем вторую цифру и так далее.

Допустим, нам нужно получить $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$ стало не превышать это количество.

Допустим, нам хочется перебрать все перестановки в лексикографическом порядке. Как это можно сделать? Напишем простую рекурсию: нам приходит префикс перестановки, и мы знаем, перестановки какой длины нам нужны. Тогда мы можем перебрать еще не использованные числа от 1 до $n$ по возрастанию (ведь интересен лексикографический порядок), поставить это число следующим и запуститься от нового префикса. Напишем код:

void f(int n, vector<int> & a, vector<char> & used) { // vector<bool> работает долго
    if (a.size() == n) { // получили новую перестановку в векторе a. Можем вывести/сохранить ее
        ...
    }
    a.push_back();
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            used[i] = true;
            a.back() = i;
            f(n, a, used);
            used[i] = false;
        }
    }
    a.pop_back();
}

Аналогичным образом можно перебирать, например, сочетания, правильные скобочные последовательности (поддерживая префикс и текущий баланс) и прочие радости.

Но вернемся к перестановкам. Кажется, что перебор всех их - весьма частая и простая задача, для которой должно быть что-то в стандартной библиотеке. Так и есть. Напишем код для перебора всех перестановок (опять же в лексикографическом порядке) с использованием встроенной функции next_permutation():

sort(a.begin(), a.end());  // чтобы перебрать все перестановки с next_permutation, нужно чтобы a изначально был отсортирован
do {
    ... // получили очередную перестановку
} while (next_permutation(a.begin(), a.end()));

Эта задача обратна по смыслу к генерации объекта по номеру. Но принцип остается тем же. Рассмотрим решение на примере перестановок.

Зададим перестановку $(a_1, a_2, \\dots, a_n)$.

Первый элемент - $a_1$. Значит, гарантированно все перестановки, начинающиеся на числа от $1$ до $a_1 - 1$ будут меньше данной. Давайте посчитаем, сколько таких. Их в точности $(n-1)! \cdot (a_1 - 1)$. То есть мы пропустили в лексикографическом порядке $a_1 - 1$ класс перестановок (деление на классы происходит по первому элементу), в каждом классе $(n-1)\!$ элементов, потому что один элемент перестановки уже задан, осталось определить порядок остальных $n-1$.

После того как мы прибавили число пропущенных перестановок к счетчику, переходим ко второму элементу, сужая класс рассматриваемых перестановок до тех, что начинаются с $a_1$. Это можно сделать, так как мы учли все перестановки с другим первым элементом. А теперь мы делаем все то же самое, но уже для перестановки из $n-1$ элементов. Заметим, что из нашего поля выпадает элемент $a_1$. Поэтому все оставшиеся числа $a_2, \dots , a_n$ уже нельзя рассматривать просто так. Например, если $a_2 > a_1$, то меньше нас будет не $(a_2 - 1) \cdot (n-2)!$ перестановок, а $(a_2 - 2) \\cdot (n-2)\!$. Таким образом, нам надо перенумеровать оставшиеся числа номерами от $1$ до $N-1$, сохраняя их относительный порядок, и работать уже с перенумерованной последовательностью.

Пример: перестановки из пяти элементов. Объект : $(2, 4, 5, 1, 3)$

$Num(x)$ будет обозначать порядковый номер числа $x$ в текущем наборе элементов. Например, если остались числа $(1, 2,5, 9, 11)$, то $Num(5) = 3$. Каждый раз пересчитываем $Num$, предварительно вычеркнув все обработанные числа $a_1 \\dots a_{k-1}$, если сейчас мы на $a_k$.

$a_1 = 2 \\Rightarrow ans += (2 - 1) \\cdot (5-1)\! = 4\! = 24$
$a_2 = 4 \Rightarrow Num(a_2) = 3 \Rightarrow ans += (3 - 1) \cdot (4 - 1)! = 2 \cdot 6 = 12$
$a_3 = 5 \Rightarrow Num(a_3) = 3 \Rightarrow ans += (3 - 1) \cdot (3 - 1)! = 2 \cdot 2 = 4$
$a_4 = 1 \\Rightarrow Num(a_4) = 1 \\Rightarrow ans += 0 $
$a_5 = 3 \\Rightarrow Num(a_5) = 1 \\Rightarrow ans += 0$
$ans = 40$