Изменения

'''Инверсией''' (англ. ''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<sup>2</восстановления sup>) == Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.Алгоритм построения в псевдокоде выглядит так: T[1..n] = 0 '''for''' i = 1..n '''for''' j = 1..(i - 1) '''if''' P[j] > P[i] T[P[i]] = T[P[i]]++Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Сортировка_слиянием |сортировку слиянием.]]

Ниже описанные алгоритмы работают == Алгоритм построения за время ОO(n^2), но их можно ускорить до О(n*N log(n)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(не умаляя общности длина равна nls1[it1]) и на n 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; ищем число i )] '''else''' '''return''' inverses_merge(от n-1 до 1inverses_get(ls.first_half) в таблице перестановки, и смотрим: сколько чисел больше i находится слева от числа i, полученное число записываем в таблицу инверсий на i-тое местоinverses_get(ls.second_half))

Для восстановления таблицы перестановки из таблицы инверсийСложность представленного алгоритма есть <tex>O(не умаляя общности длина таблицы равна n) создаем таблицу, которую будем расширять, по мере добавления в неё чисел, добавляем в эту таблицу число i (где i от \log n до 1) на позицию k+1, где k - число в таблице инверсий на i-том месте</tex>. Алгоритм с такой же сложностью можно построить с помощью [[Дерево_отрезков._Построение | дерева отрезков.]]

== Алгоритм построения за O(N) == Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой]]. При [[Карманная сортировка | карманной сортировке]] нужно определить карман <tex>B</tex>, в который попадет текущий элемент. Затем найти число элементов в старших карманах относительно <tex>B</tex>. Потом аккуратно подсчитать количество элементов, больших текущего в кармане <tex>B</tex>. Карман <tex>A</tex> считается старшим для кармана <tex>B</tex>, если любой элемент из <tex>A</tex> больше любого элемента из <tex>B</tex>.    '''int''' bucket_sort('''vector<int>''' permutation): '''int''' max = число больше permutation.size и из которого можно извлечь целый квадратный корень '''int''' bucket = sqrt(max) '''int''' answer = 0<font color=green> // изначально кол-во инверсий</font> '''list<list<int>>''' bank(bucket) '''for''' i = 0 to permutation.size '''int''' pos = (permutation[i] - 1) / (max / bucket) <font color=green>// Определяем в каком кармане должен лежать элемент</font> '''int''' newPosition = 0 '''while''' newPosition < bank[pos].size '''and''' bank[pos][newPosition] < permutation[i] <font color=green>// идем до позиции где должен стоять элемент permutation[i] </font> newPosition++ answer += bank[pos].size - newPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font> bank[pos].insert(newPosition, permutation[i]) <font color=green>// вставляем элемент в Карман на свою позицию </font> '''for''' i = position + 1 to bucket - 1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font> answer += bank[i].size '''return''' answer В разделе [[Карманная сортировка | карманная сортировка]] доказывается, что она работает за линейное время. Что касается подсчета инверсий, то в приведенной реализации происходит [[Карманная сортировка | карманная сортировка]] в online режиме и вся математическая часть подходит и под этот случай. Следует отметить, что хотя подсчет с помощью [[Карманная сортировка | карманной сортировки]] выполняется за линейное время, но имеет очень большую константу поэтому подсчет инверсий рассматриваемый выше за <tex>O(n\log n)</tex> работает быстрее . == Алгоритм восстановления == Для восстановления перестановки по таблицы инверсий <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[i] == 0 '''if''' j == k result[i] = curr '''break''' '''else:''' j++ curr++ '''return''' result  Этот простой алгоритм имеет сложность <tex>O(n^2)</tex> — внутренний цикл делает до <tex>n</tex> итераций, внешний — ровно <tex>n</tex> итераций. Видно, что для восстановления нужно узнавать <tex>k</tex>-ую свободную позицию. Это можно делать с помощью [[Дерево_отрезков._Построение | дерева отрезков]] следующим образом: построим дерево отрезков для суммы на массиве из единиц. Единица в позиции означает, что данная позиция свободна. Чтобы найти <tex>k</tex>-ую свободную позицию, нужно спускаться (начиная с корня) в левое поддерево если сумма в нём больше, чем <tex>k</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 \log n)</tex>: делается <tex>n</tex> итераций цикла, в которой происходит спуск по дереву высоты <tex>O(\log n)</tex> и один запрос на дереве отрезков. Таким образом, время работы алгоритма на каждой итерации есть <tex>O(\log n)</tex>. == Пример == Рассмотрим пример построения таблицы инверсий и восстановления перестановки по таблице инверсий. Пусть дана перестановка <tex>(5, 7, 1, 3, 4, 6, 8, 2)</tex>. Следующая таблица показывает работу алгоритма за <tex>O(n \log n)</tex>, на каждой строке один уровень рекурсии (на первой строке — самый глубокий). В скобках стоят пары: элемент перестановки, количество инверсий. Полужирным отмечены элементы, у которых обновилось значение количества инверсий на данном шаге. {|widthstyle = "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, 0)| style = "background-color: white; padding: 3px 6px" |(1, 0)| style = "background-color: white; padding: 3px 6px" |(3, 0)| style ="150background-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" align|(2, 0)|-|colspan ="right2" cellpaddingstyle ="background-color: white; padding: 3px 6px"|(5, 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, 0)|colspan = "2" borderstyle = "background-color: white; padding: 3px 6px"|'''(2, 1)''', (8, 0)|-|colspan = "4" style ="background-color: white; padding: 3px 6px"|'''(1, 2)''', '''(3, 2)''', (5, 0), (7, 0)|colspan = "4" style="borderbackground-collapsecolor: collapsewhite;padding: 3px 6px"|'''(2, 3)''', (4, 0), (6, 0), (8, 0)

| <span colspan = "8" style="fontbackground-sizecolor:smallerwhite;padding: 3px 6px">Получение таблицы перестановки из таблицы инверсии</span> [|(1, 2), '''(2 , 6)''', (3 6 , 2), '''(4 0 , 2 2 1 )''', (5, 0] - т. инверсии [9] [9 8] [9 8 7] [9 8 ), '''(6 , 1)''', (7] [5 9 , 0), (8 6 7], 0) [5 9 8 6 4 7]|} [5 9 8 6 4 7 3] [5 9 8 Полученная таблица инверсий: <tex>(2 , 6 4 7 3] [5 9 , 2, 2, 0, 1 8 2 6 4 7 3] - т, 0, 0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива. перестановки|-}

{|widthstyle = "border: 0px solid; background-color: grey; text-align: center; padding : 0;" cellspacing ="1502" |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" 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: #EEF; text-align: left; 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>1</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan ="right1" cellpaddingstyle ="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" 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</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>\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</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{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</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>\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</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</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</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 = " borderbackground-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex>|colspan ="1" style="borderbackground-color: #EEF; text-collapsealign: collapseleft;padding: 3px 6px"|не пропускаем свободных позиций и ставим <tex>\bf{7}</tex>

| colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5<span /tex>|colspan = "1" style="fontbackground-sizecolor:smallerwhite;padding: 3px 6px"|<tex>Получение таблицы инверсии из таблицы перестановки7</spantex> [5 9 |colspan = "1 8 2 6 4 7 3] " style = "background- т. перестановкиcolor: white; padding: 3px 6px"|<tex>1</tex> [ 0]|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex> [ |colspan = "1 0]" style = "background-color: white; padding: 3px 6px"|<tex>4</tex> [ 2 |colspan = "1 0]" style = "background-color: white; padding: 3px 6px"|<tex>6</tex> [ 2 2 |colspan = "1 0]" style = "background-color: white; padding: 3px 6px"|<tex>\bf{8}</tex> [ 0 2 |colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2 </tex>|colspan = "1 0]" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|не пропускаем свободных позиций и ставим <tex>\bf{8}</tex>|} == См. также == * [[ 4 0 2 2 1 0Матричное представление перестановок]] == Источники информации == * [ 6 4 0 2 2 1 0https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation] * Д. Кнут - Искусство программирования, том 3 {{---}} 29-31 с.  [[ 3 6 4 0 2 2 1 0Категория: Дискретная математика и алгоритмы]] [2 3 6 4 0 2 2 1 0[Категория: Комбинаторика ]] - т. инверсии|-}