Изменения

Пусть <wikitextex>Пусть $ P = (p_1,p_2,\dots,p_n)$ </tex> является [[Действие перестановки на набор из элементов, представление в виде циклов|перестановкой]] чисел $ <tex> 1, 2,\dots, n$</tex>.

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

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

Сложность данного алгоритма {{---}} $<tex>O(n^2)$</tex>. Уменьшить время работы можно используя [[Дерево отрезков. Построение|дерево отрезков]].

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

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

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

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

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

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

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

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

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

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

 * $[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]$  Получаем перестановку $<tex>[10, 2, 7, 5, 1, 4, 6, 8, 3, 9]$</tex>