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

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

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

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

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

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

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

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

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

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

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

[math]T[i] = Sum(M[i])[/math] 

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

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

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

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

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

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

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

$([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.$

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

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

Пример

• [math][4, 1, 6, 3, 2, 2, 1, 1, 1, 0][/math] - таблица инверсий.
• [math][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][/math]
• [math][1,2][2,1]\circ[3,4][2,3], [2,5][0,6]\circ[1,7][0,8], [0,10][0,9][/math]
• [math][1,2][2,1][0,4][2,3]\circ[1,7][0,5][0,6][0,8], [0,10][0,9][/math]
• [math][1,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3]\circ[0,10][0,9][/math]
• [math][0,10][0,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3][0,9][/math]

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

Источники

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