Перестановки

Иногда в задачах требуется подсчитать количество некоторых объектов, количество способов сделать что-то. При этом обычно это количество слишком велико, чтобы можно было перечислить все объекты в явном виде.

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

Принято считать, что $0\!=1$

Возведение перестановки в k-ую степень

Условие. Дана перестановка p длины n. Требуется возвести её в k-ую степень, т.е. найти, что получится, если к тождественной перестановке k раз применить перестановку p.

Решение. Просто применим к перестановке p описанный выше алгоритм бинарного возведения в степень. Никаких отличий по сравнению с возведением чисел в степень — нет. Решение получается с асимптотикой O (n \log k).

(Примечание. Данную задачу можно решить и более эффективно, за линейное время. Для этого достаточно выделить в перестановке все циклы, после чего рассмотреть по отдельности каждый цикл и, взяв k по модулю длины текущего цикла, найти ответ для этого цикла.)

Также бинарное возведение в степень можно применить в задачах:

Возведение перестановки в $n$-ую степень: можно показать, что перемножение перестановок (применение одной к другой) тоже ассоциативно, а значит можно воспользоваться бинарным возведением в степень, где вместо произведения чисел будет применение перестановки за $O(n)$. (Однако, данную задачу можно решить и более эффективно, за линейное время: для этого достаточно найти в перестановке все циклы, после чего рассмотреть по отдельности каждый цикл и, взяв $n$ по модулю длины текущего цикла, найти ответ для этого цикла.)

Задача

Перебрать все перестановки в лексикографическом порядке

Код

int perm[MAXN];
bool used[MAXN];
void gen(int cur_index) {
  if (cur_index == n) {
    //получена перестановка
  } else {
    for (int i = 1; i <= n; i++) {
     if (!used[i]) {
        used[i] = 1;
        perm[cur_index] = i;
        used[i] = 0;
     }
  }
}

Важное уточнение

В с++ существует функция next_permutation, которая генерируют следующую перестановку, следовательно для того чтобы сгенерировать следующую перестановку мы просто можем ее использовать, пока не найдем последнюю перестановку.

Задача

Даны натуральные числа $k$ и $n$ $s.t. 0 \\leq k \< n\!$. Надо найти $k$-ую в лексикографическом порядке перестановку чисел от $1$ до $n$. Например, для $n = 3$ и $k = 4$ надо вывести $3 1 2$.

Решение

Вспомним, что если перестановка $k$-ая в лексикографическом порядке, то существует ровно $k$ перестановок, которые меньше неё. Будем находить элементы искомой позиции по очереди слева направо, постепенно набирая (неявно) те самые $k$ перестановок, которые меньше нас.

Если мы поставим на первое место не $1$, а $2$, то мы заведомо получим перестановку, которая больше всех перестановок, которые начинаются на $1$, а их $(n-1)\!$. Если мы поставим на первое место не $2$, а $3$, то перестановок, которые меньше нас уже $2 \\cdot (n-1)\!$ итд. Значит, давайте увеличивать первую цифру до тех пор, пока можем (пока $(d-1) \cdot (n-1)! \leq k)$. Затем вычтем из $k$ то число перестановок, которых мы уже заведомо лексикографически больше, и начнём перебирать вторую цифру, теперь уже вычитая $(n-2)\!$, пока можно. Разумеется, каждый раз перебирая цифру на очередную позицию, мы будем пропускать цифры, которые мы уже поставили ранее.

Корректность

Посколько классы перестановок, которые мы вычитаем, не пересекаются, то в конце мы получим перестановку $\\sigma$, для которой существует ровно $k$ перестановок, которые лексикографически меньше $\\sigma$.

Задача

Дана перестановка, требуется получить ее номер в лексикографическом порядке

Идея

Заметим, что для каждой позиции нас интересует только то сколько меньших лексикографически вариантов могло стоять на этой позиции, так как любой вариант меньше на этой позиции дает меньшие перестановки независимо от суффикса, следовательно давайте для каждой позиции посчитаем сумму сколько вариантов меньше из-за того, что число на этой позиции меньше

Решение

Номер перестановки = $\sum \limits_{i} \sum \limits_{i \< j} a[i] > a[j] \cdot (n - i)!$

Задача

Дана перестановка чисел от $1$ до $n$. Надо по ней сгенерировать следующую в лексикографическом порядке.

Решение

Пусть $i \~-$ первый элемент последовательности при проходе справа налево, для которого $a\[i\] \\leqslant a\[i + 1\]$.
Пусть $j \~-$ индекс минимального элемента справа от $i$, который больше $a\[i\]$.
Сделаем $swap(i, j)$, после чего суффикс, начиная с $i$ позиции отсортирован в порядке убывания.
Развернём суффикс, начиная с $i+1$.

Доказательство корректности

Чтобы доказать корректность, надо доказать:

Что получившаяся последовательность лексикографически больше исходной
Что не существует последовательности, которая лексикографически больше исходной, но лексикографически меньше получившейся.

Решим следующую задачу - пусть дана перестановка/сочетание/размещение, надо по ней сгенерировать следующий в лексикографическом порядке объект.

Например, перестановки из 8 элементов:

$(1, 5, 2, 3, 4, 8, 7, 6) \\Rightarrow (1, 5, 2, 3, 6, 4, 7, 8)$

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

Перестановки

Что это значит для перестановок? Посмотрим на тот же пример. Будем постепенно увеличивать суффикс и проверять, можно ли его увеличить.

$(1, 5, 2, 3, 4, 8, 7, \[6\])$ Одну шестерку никак не изменить
$(1, 5, 2, 3, 4, 8, \[7, 6\])$ Суффикс - (7,6) из семерки и шестерки нельзя собрать ничего большего
$(1, 5, 2, 3, 4, \[8, 7, 6\])$ Суффикс - (8,7,6), тут тоже элементы образуют максимальную возможную перестановку между собой.
$(1, 5, 2, 3, \[4, 8, 7, 6\])$ Вот теперь суффиксом будет $(4, 8, 7, 6)$, мы можем его увеличить. Для этого на первую позицию в суффиксе поставим следующее за четверкой число, в данно случае это 6, а потом оставшиеся числа расставим так, чтобы конец получился наименьшим возможным. То есть ставим шестерку на первое место, а оставшиеся числа расставим по возрастанию.

Сочетания

Сохраняем тот же принцип, каждое сочетание представляет собой отсортированную последовательность чисел от $1$ до $N$ длины $K$. Значит, будем искать такой суффикс, в котором можно увеличить первый элемент за счет чисел, не использованных в префиксе. Оставшийся суффикс будет логично дополнить последовательными числами, они точно не использовались в префиксе, так как последовательность всегда отсортирована.

Рассмотрим пример: $C_6^4$

$(1, 2, 5, 6)$

Ни суффикс $(6)$, ни $(5,6)$ увеличить нельзя, можем взять только $(2, 5, 6)$. Значит, заменим $2$ на $3$, а дальше дополним последовательными числами - $(3, 4, 5)$.

По сути критерий того, что суффикс можно увеличить заключается в том, что он не является суффиксом последовательности $1, 2, 3, \dots, N - 1, N$

Как получить предыдущий

Здесь наоборот надо найти минимальный суффикс, который можно уменьшить. Как правильно изменить найденный суффикс - первый элемент в суффиксе изменяем на предыдущий возможный, а остальной суффикс делаем максимальным из всех возможных.

Рассмотрим пример для перестановок из восьми элементов:

$(1, 5, 2, 3, 6, 4, 7, 8) \Rightarrow (1, 5, 2, 3, [6, 4, 7, 8]) \Rightarrow (1, 5, 2, 3, 4, 8, 7, 6)$