Изменения

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

'''Таблицей инверсий''' (англ. ''inversion table'') перестановки <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>.

== Алгоритм построения за O(N²) ==

For '''for''' i = 1..n For '''for''' j = 1..(i - 1) '''if ''' P[j] > P[i] T[P[i]] = T[P[i]] + 1+Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Дерево отрезковСортировка_слиянием |сортировку слиянием.]] == Алгоритм построения за O(N log N) == Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. ПостроениеБудем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично [[Сортировка_слиянием |дерево отрезковсортировке слиянием.]] Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количество нерассмотренных элементов первого списка. Описанный алгоритм записывается в псевдокод следующим образом: <font color=green>// ''inverses_merge'' {{---}} процедура, сливающая два списка пар</font> <font color=green>// ''inverses_get'' {{---}} процедура, рекурсивно получающая таблицу инверсий для перестановки</font> '''def''' inverses_merge(ls1, ls2): result = [] it1, it2 = ''null'' '''while''' (it1 < ls1.length) '''and''' (it2 < ls2.length) '''if''' ls1[it1].item < ls2[it2].item result.append(ls1[it1]) it1++ '''else''' result.append(item = ls2[it2].item, inverses = ls2[it2].inverses + ls1.length - it1) it2++ '''while''' it1 < ls1.length result.append(ls1[it1]) it1++ '''while''' it2 < ls2.length result.append(ls2[it2]) it2++ '''return''' result '''def''' inverses_get(ls): '''if''' ls.length == 1 '''return''' [(item = ls[0], inverses = 0)] '''else''' '''return''' inverses_merge(inverses_get(ls.first_half), inverses_get(ls.second_half))

Данная формула даёт правильный ответ, так как Сложность представленного алгоритма есть <tex>S[M[i]]O(n\log n)</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_2nN)</tex>==

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

Для восстановления таблицы перестановки из таблицы инверсий создаем таблицу, которую будем расширять, по мере добавления в неё чисел. Добавляем в эту таблицу число '''int''' bucket_sort('''vector<tex>i</texint> ''' permutation): '''int''' max = число больше permutation.size и из которого можно извлечь целый квадратный корень '''int''' bucket = sqrt(где max) '''int''' answer = 0<texfont color=green>i// изначально кол-во инверсий</texfont> от '''list<list<texint>n</tex> до ''' bank(bucket) '''for''' i = 0 to permutation.size '''int''' pos = (permutation[i] - 1) на позицию / (max / bucket) <texfont color=green>k+1// Определяем в каком кармане должен лежать элемент</texfont>, где '''int''' newPosition = 0 '''while''' newPosition < bank[pos].size '''and''' bank[pos][newPosition] < permutation[i] <texfont color=green>k// идем до позиции где должен стоять элемент permutation[i] </texfont> newPosition++ answer += bank[pos].size - число в таблице инверсий на newPosition <texfont color=green>i// ищем сколько инверсий эленент создает в своем кармане</texfont>-том месте bank[pos]. Данный алгоритм довольно прост в реализацииinsert(newPosition, но без использования дополнительных структур данных, имеет сложность permutation[i]) <texfont color=green>O(n^2)// вставляем элемент в Карман на свою позицию </texfont>, т. к. для вставки элемента в определённую позицию, требуется порядка '''for''' i = position + 1 to bucket - 1 <texfont color=green>n// ищем сколько инверсий он создает с элементами в других карманах</texfont> перестановок элементов answer += bank[i].size '''return''' answer

Приведём алгоритм восстановления с использованием В разделе [[Сортировка слияниемКарманная сортировка |сортировки слияниемкарманная сортировка]]доказывается, имеющий сложность <tex>O(n\log_2n)</tex>что она работает за линейное время. Что касается подсчета инверсий, то в приведенной реализации происходит [[Карманная сортировка | карманная сортировка]] в online режиме и вся математическая часть подходит и под этот случай.

Пусть <tex>\alpha</tex> и <tex>\beta</tex> - цепочки упорядоченных пар целых неотрицательных чисел <tex>Следует отметить, что хотя подсчет с помощью [[m_1, n_1Карманная сортировка | карманной сортировки]]\dots[m_kвыполняется за линейное время, n_k]но имеет очень большую константу поэтому подсчет инверсий рассматриваемый выше за </tex>. Рассмотрим двоичную операцию <tex>\circ</tex>, рекурсивно определенную на парах таких цепочек следующим образом: $O([m, n]\alpha)\circ([m', log 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</tex>m'.\\ \end{aligned} \rightработает быстрее .$

Цепочка наподобие Для восстановления перестановки по таблицы инверсий <tex>T</tex> воспользуемся следующим соображением: единица стоит в перестановке на <tex>T_0</tex>-ом месте (индексируем элементы с нуля), так как остальные числа в перестановке больше единицы. Далее, если известны расположения всех чисел <tex>1, \dots, k</tex>, то число <tex>k + 1</tex> стоит на <tex>T_{k + 1}</tex>-ой ещё не занятой позиции: все числа, меньшие <tex>k + 1</tex> уже расставлены. Это рассуждение напрямую переписывается в код следующим образом: <font color=green>// ''j'' {{---}} счётчик пропущенных свободных позиций</font> <font color=green>// ''k'' {{---}} количество инверсий слева для элемента curr</font> <font color=green>// ''result'' {{---}} массив, в который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.</font> '''def''' recover_straight(ls): n = ls.length result = array(0, n) curr = 1 '''for''' k '''in''' ls j = 0 '''for''' i = 0..(n - 1) '''if''' result[4, 4i]== 0 '''if''' j == k result[1i] = curr '''break''' '''else:''' j++ curr++ '''return''' result  Этот простой алгоритм имеет сложность <tex>O(n^2)</tex> — внутренний цикл делает до <tex>n</tex> итераций, внешний — ровно <tex>n</tex> итераций. Видно,3что для восстановления нужно узнавать <tex>k</tex>-ую свободную позицию. Это можно делать с помощью [[Дерево_отрезков._Построение | дерева отрезков]]следующим образом: построим дерево отрезков для суммы на массиве из единиц. Единица в позиции означает, что данная позиция свободна. Чтобы найти <tex>k</tex> представляет "_ _ _ _ 4 _ 3 _ -ую свободную позицию, нужно спускаться (начиная с корня) в левое поддерево если сумма в нём больше, чем <tex>\inftyk</tex>", где "_" означает пропуски в правое дерево иначе. Данный алгоритм переписывается в код следующим образом:  <font color=green>// ''build_segment_tree'' {{---}} строит дерево отрезков над массивом</font> <font color=green>// ''node'' {{---}} вершина дерева</font> <font color=green>// ''node.index'' {{---}} индекс соответствующего элемента в массиве для листа дерева</font> '''def''' recover(inv): n = inv.length tree = build_segment_tree(array(n, 1)) result = array(n) curr = 1 '''for''' k '''in''' inv node = tree.root '''while''' !node.is_leaf '''if''' k < node.left.value node = node.left '''else''' k -= node.left.value node = node.right result[node.index] = curr node. Операция add(-1) curr++ '''return''' result  Этот алгоритм имеет сложность <tex>O(n \alpha \circ \betalog n)</tex>: делается <tex>n</tex> вставляет пропуски и заполнения из итераций цикла, в которой происходит спуск по дереву высоты <tex>O(\betalog n)</tex> и один запрос на дереве отрезков. Таким образом, время работы алгоритма на место пропусков в каждой итерации есть <tex>O(\alphalog n)</tex>.

* Рассмотрим пример построения таблицы инверсий и восстановления перестановки по таблице инверсий. Пусть дана перестановка <tex>[4(5, 7, 1, 6, 3, 24, 26, 18, 1, 1, 0]2)</tex> - . Следующая таблица инверсий.* показывает работу алгоритма за <tex>O(n \log n)</tex>[4,1]\circ[1на каждой строке один уровень рекурсии (на первой строке — самый глубокий). В скобках стоят пары: элемент перестановки, количество инверсий. Полужирным отмечены элементы,у которых обновилось значение количества инверсий на данном шаге. {| style = "border: 0px solid; background-color: gray; text-align: center; padding : 0" cellspacing = "2]"| style = "background-color: white; padding: 3px 6px" |(5, 0)| style = "background-color: white; padding: 3px 6px" |(7, [60)| style = "background-color: white; padding: 3px 6px" |(1,3]\circ[0)| style = "background-color: white; padding: 3px 6px" |(3,0)| style = "background-color: white; padding: 3px 6px" |(4], [0)| style = "background-color: white; padding: 3px 6px" |(6, 0)| style = "background-color: white; padding: 3px 6px" |(8, 0)| style = "background-color: white; padding: 3px 6px" |(2,0)|-|colspan = "2" style = "background-color: white; padding: 3px 6px"|(5]\circ[, 0), (7, 0)|colspan = "2" style = "background-color: white; padding: 3px 6px"|(1, 0), (3, 0)|colspan = "2" style = "background-color: white; padding: 3px 6px"|(4,0), (6], [10)|colspan = "2" style = "background-color: white; padding: 3px 6px"|'''(2,7]\circ[1)''',(8], [0)|-|colspan = "4" style = "background-color: white; padding: 3px 6px"|'''(1,9]\circ[2)''', '''(3, 2)''', (5, 0), (7, 0)|colspan = "4" style = "background-color: white; padding: 3px 6px"|'''(2, 3)''', (4, 0), (6, 0), (8,10]</tex>0)|-* <tex>[|colspan = "8" style = "background-color: white; padding: 3px 6px"|(1,2][), '''(2,1]\circ[6)''', (3,4][2),3]'''(4, [2)''',(5][, 0),'''(6]\circ[, 1)''',(7][, 0),(8], [0)|} Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0,10][1, 0,9]0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива. {| style = "border: 0px solid; background-color: grey; text-align: center; padding : 0;" cellspacing = "2"|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{1}</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>* |colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>[0</tex>|colspan = "1,2][2," style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1][" style = "background-color: white; padding: 3px 6px"|<tex>0,4][2,3]</tex>|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем две свободных позиции и ставим <tex>\circ[bf{1}</tex>|-|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1,7][" style = "background-color: white; padding: 3px 6px"|<tex>0,5][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,6][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,8], [</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,10][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,9]</tex>* |colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{2}</tex>[|colspan = "1," style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем шесть свободных позиций и ставим <tex>\bf{2][}</tex>|-|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,7][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,5][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{3}</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,</tex>|colspan = "1][" style = "background-color: white; padding: 3px 6px"|<tex>0,4][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,6][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex>|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем две свободных позиции и ставим <tex>\bf{3}</tex>|-|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,8][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3]</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\circ[bf{4}</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,10][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex>|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем две свободных позиции и ставим <tex>\bf{4}</tex>|-|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{5}</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,9]</tex>* |colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>4</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>[0,10][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2][</tex>|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|не пропускаем свободных позиции и ставим <tex>\bf{5}</tex>|-|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>4</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{6}</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex>|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем одну свободную позицию и ставим <tex>\bf{6}</tex>|-|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{7][}</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>4</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>6</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex>|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|не пропускаем свободных позиций и ставим <tex>\bf{7}</tex>|-|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5]</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>7</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>4</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>6</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{8}</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex>|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|не пропускаем свободных позиций и ставим <tex>\bf{8}</tex>|} == См. также ==* [0,1][0,4Матричное представление перестановок][0,6] == Источники информации == * [0,8https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation][0* Д. Кнут - Искусство программирования,том 3][0,9]</tex>{{---}} 29-31 с.