Таблица инверсий

<wikitex> Пусть $ P = (p_1,p_2,\dots,p_n)$ является перестановкой чисел $ 1, 2,\dots, n$.

Определение:

Инверсией в перестановке $P$ называется всякая пара индексов $i, j$ такая, что $1\leqslant i<j\leqslant n$ и $P[i]>P[j]$.

Определение:

Таблицей инверсий перестановки $ P $ называют такую последовательность $ T = (t_1,t_2,\dots,t_n)$, в которой $t_i$ равно числу элементов перестановки $ P $, стоящих в $ P $ левее числа $i$ и больших $i$.

Алгоритм построения

Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него. Алгоритм построения в псевдокоде выглядит так:

T[1..n] = 0
For i = 1..n
  For j = 1..(i - 1)
    if P[j] > P[i]
      T[P[i]] = T[P[i]] + 1

Сложность данного алгоритма — $O(n^2)$. Уменьшить время работы можно используя дерево отрезков.

Получим из исходной перестановки обратную и запишем её в массив $M$. Также заведём массив $S$ длиной $n$, инициализированный нулями. После обработки $i$-го элемента будем вносить значение 1 в ячейку $S[M[i]]$. Обработку начинаем с последнего элемента и двигаемся к началу. Пусть, функция $Sum(i)$ возвращает значение суммы элементов массива $S$ от 1 до $i$. Тогда $i$-й элемент таблицы инверсий находится так:

$T[i] = Sum(M[i])$ 

Данная формула даёт правильный ответ, так как $S[M[i]]$ содержит единицу только в том случае, если мы уже обработали элемент, стоящий в $M[i]$-й позиции. Так как обработка идёт от больших чисел к меньшим, $Sum(M[i])$ выдаст нужное нам количество чисел, больших $i$ и стоящих в перестановке левее него.

Функция $Sum$ реализуется с помощью дерева отрезков. Каждое изменение массива и обращение к функции $Sum$ влечёт за собой $\log_2n$ операций. Таким образом получаем сложность алгоритма $O(n\log_2n)$

Также существует достаточно простой алгоритм построения таблицы инверсий с использованием сортировки слиянием. Вначале выписываются следующие упорядоченные пары чисел: в $i$-ой паре на первом месте стоит $i$-й элемент перестановки, а на втором — 0. Далее применяется сортировка слиянием, при чем при выписывании элемента из второй цепочки упорядоченных пар, число на второй позиции в данном элементе увеличивается на количество элементов, оставшихся в первой цепочке. В конце сортировки получим цепочку упорядоченных пар. Выписывая вторые элементы данных упорядоченных пар, получим искомую таблицу инверсий. Сложность данного алгоритма совпадает со сложностью сортировки слиянием и составляет $O(n\log_2n)$.

Алгоритм восстановления

Для восстановления таблицы перестановки из таблицы инверсий создаем таблицу, которую будем расширять, по мере добавления в неё чисел. Добавляем в эту таблицу число $i$ (где $i$ от $n$ до 1) на позицию $k+1$, где $k$ - число в таблице инверсий на $i$-том месте. Данный алгоритм довольно прост в реализации, но без использования дополнительных структур данных, имеет сложность $O(n^2)$, т. к. для вставки элемента в определённую позицию, требуется порядка $n$ перестановок элементов.

Приведём алгоритм восстановления с использованием сортировки слиянием, имеющий сложность $O(n\log_2n)$.

Пусть $\alpha$ и $\beta$ - цепочки упорядоченных пар целых неотрицательных чисел $[m_1, n_1]\dots[m_k, n_k]$. Рассмотрим двоичную операцию $\circ$, рекурсивно определенную на парах таких цепочек следующим образом:

$([m, n]\alpha)\circ([m', n']\beta)=\left\{\begin{aligned}[]
[m,n](\alpha \circ ([m'-m, n']\beta)), m \le m',\\
[m', n'](([m-m'-1, n]\alpha) \circ \beta), m>m'.\\
\end{aligned}
\right.$

Сопоставим каждому элементу таблицы инверсий его номер. Получится множество упорядоченных пар чисел $[m_1, n_1]\dots[m_k, n_k]$, где $m_i$ — сам элемент, а $n_i$ — его номер. Разобьём данные элементы на пары и произведём с ними операцию $\circ$. Получим некоторое количество цепочек упорядоченных пар. Также разбиваем их на пары и производим операцию $\circ$. Так действуем, пока не останется одна цепочка. Выписывая вторые элементы данных упорядоченных пар в том порядке, в каком они представлены в цепочке, получим первоначальную перестановку.

Цепочка наподобие $[4, 4][1,3]$ представляет "_ _ _ _ 4 _ 3 _ $\infty$", где "_" означает пропуск. Операция $\alpha \circ \beta$ вставляет пропуски и заполнения из $\beta$ на место пропусков в $\alpha$.

Пример

• $[4, 1, 6, 3, 2, 2, 1, 1, 1, 0]$ - таблица инверсий.

• $[4,1]\circ[1,2], [6,3]\circ[3,4], [2,5]\circ[2,6], [1,7]\circ[1,8], [1,9]\circ[0,10]$

• $[1,2][2,1]\circ[3,4][2,3], [2,5][0,6]\circ[1,7][0,8], [0,10][0,9]$

• $[1,2][2,1][0,4][2,3]\circ[1,7][0,5][0,6][0,8], [0,10][0,9]$

• $[1,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3]\circ[0,10][0,9]$

• $[0,10][0,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3][0,9]$

Получаем перестановку $[10, 2, 7, 5, 1, 4, 6, 8, 3, 9]$

Источники

• Д. Кнут - Искусство программирования, том 3.

</wikitex>