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

<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])$ 

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

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

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

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

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

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

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

Пример

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

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

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

$[1,2][2,1][0,4][2,3]o[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]o[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>