http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=109.187.33.19&*
Викиконспекты - Вклад участника [ru]
2026-04-07T00:36:56Z
Вклад участника
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0_%D0%B8%D0%BD%D0%B2%D0%B5%D1%80%D1%81%D0%B8%D0%B9&diff=58420
Таблица инверсий
2016-12-29T19:32:47Z
<p>109.187.33.19: /* Алгоритм построения за O(N) */</p>
<hr />
<div>Пусть <tex> P = (p_1,p_2,\dots,p_n)</tex> является [[Действие перестановки на набор из элементов, представление в виде циклов|перестановкой]] чисел <tex> 1, 2,\dots, n</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
'''Инверсией''' (англ. ''inversion'') в перестановке <tex>P</tex> называется всякая пара индексов <tex>i, j</tex> такая, что <tex>1\leqslant i<j\leqslant n</tex> и <tex>P[i]>P[j]</tex>.<br />
}}<br />
{{Определение<br />
|definition = <br />
'''Таблицей инверсий''' (англ. ''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>.<br />
}}<br />
<br />
== Алгоритм построения за O(N<sup>2</sup>) ==<br />
<br />
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.<br />
Алгоритм построения в псевдокоде выглядит так: <br />
T[1..n] = 0<br />
'''for''' i = 1..n<br />
'''for''' j = 1..(i - 1)<br />
'''if''' P[j] > P[i]<br />
T[P[i]] = T[P[i]]++<br />
Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Сортировка_слиянием |сортировку слиянием.]]<br />
<br />
== Алгоритм построения за O(N log N) ==<br />
<br />
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично [[Сортировка_слиянием |сортировке слиянием.]]<br />
<br />
Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количество нерассмотренных элементов первого списка.<br />
<br />
Описанный алгоритм записывается в псевдокод следующим образом:<br />
<font color=green>// ''inverses_merge'' {{---}} процедура, сливающая два списка пар</font><br />
<font color=green>// ''inverses_get'' {{---}} процедура, рекурсивно получающая таблицу инверсий для перестановки</font><br />
'''def''' inverses_merge(ls1, ls2):<br />
result = []<br />
it1, it2 = ''null''<br />
'''while''' (it1 < ls1.length) '''and''' (it2 < ls2.length)<br />
'''if''' ls1[it1].item < ls2[it2].item<br />
result.append(ls1[it1])<br />
it1++<br />
'''else'''<br />
result.append(item = ls2[it2].item, inverses = ls2[it2].inverses + ls1.length - it1)<br />
it2++<br />
'''while''' it1 < ls1.length<br />
result.append(ls1[it1])<br />
it1++<br />
'''while''' it2 < ls2.length<br />
result.append(ls2[it2])<br />
it2++<br />
'''return''' result<br />
<br />
'''def''' inverses_get(ls):<br />
'''if''' ls.length == 1<br />
'''return''' [(item = ls[0], inverses = 0)]<br />
'''else'''<br />
'''return''' inverses_merge(inverses_get(ls.first_half), inverses_get(ls.second_half))<br />
<br />
<br />
Сложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью [[Дерево_отрезков._Построение | дерева отрезков.]]<br />
<br />
== Алгоритм построения за O(N) ==<br />
<br />
Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой]]. При карманной сортировке нужно определить карман <tex>B</tex>, в который попадет текущий элемент. Затем найти количество элементов в старших карманах относительно <tex>B</tex>. Потом аккуратно подсчитать количество элементов, больших текущего в кармане <tex>B</tex>. Карман <tex>A</tex> считается старшим для кармана <tex>B</tex>, если любой элемент из <tex>A</tex> больше любого элемента из <tex>B</tex>.<br />
<br />
<br />
<br />
'''int''' bucket_sort('''vector<int>''' Permutation):<br />
MAX = число больше Permutation.size и из которого можно извлечь целый квадратный корень<br />
BUCKET=sqrt(MAX)<br />
'''int''' Answer = 0<font color=green> // изначально кол-во инверсий</font><br />
'''list<list<int>>''' Bank(BUCKET)<br />
'''for''' i = 0 to Permutation.size <br />
'''int''' Position = (Permutation[i] - 1)/(MAX / BUCKET) <font color=green>// Определяем в каком кармане должен лежать элемент</font><br />
'''int''' NewPosition = 0<br />
'''while'''(NewPosition < Bank[pos].size && Bank[pos][NewPosition] < Permutation[i] ) <font color=green>// идем до позиции где должен стоять элемент Permutation[i] </font><br />
NewPosition++<br />
Answer += Bank[pos].size - NewPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font><br />
Bank[pos].insert( NewPosition , Permutation[i] ) <font color=green>// вставляем элемент в Карман на свою позицию </font><br />
'''for''' i = Position + 1 to BUCKET-1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font><br />
Answer += Bank[i].size<br />
'''return''' Answer<br />
<br />
Известно что карманная сортировка имеет линейную сложность, но только в том случае если элементы равномерно распределены. Т.к. мы ищем кол-во инверсий в перестановке то мы знаем что наши элементы встречаются на отрезке от <tex>[1;n]</tex> единожды , а следовательно равномерно распределены.<br />
<br />
Сложность представленного алгоритма есть <tex>O(n)</tex>.<br />
<br />
== Алгоритм восстановления ==<br />
<br />
Для восстановления перестановки по таблицы инверсий <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> уже расставлены. Это рассуждение напрямую переписывается в код следующим образом:<br />
<font color=green>// ''j'' {{---}} счётчик пропущенных свободных позиций</font><br />
<font color=green>// ''k'' {{---}} количество инверсий слева для элемента curr</font><br />
<font color=green>// ''result'' {{---}} массив, в который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.</font><br />
'''def''' recover_straight(ls):<br />
n = ls.length<br />
result = array(0, n)<br />
curr = 1<br />
'''for''' k '''in''' ls<br />
j = 0<br />
'''for''' i = 0..(n - 1)<br />
'''if''' result[i] == 0<br />
'''if''' j == k<br />
result[i] = curr<br />
'''break'''<br />
'''else:'''<br />
j++<br />
curr++<br />
'''return''' result<br />
<br />
<br />
Этот простой алгоритм имеет сложность <tex>O(n^2)</tex> — внутренний цикл делает до <tex>n</tex> итераций, внешний — ровно <tex>n</tex> итераций.<br />
<br />
Видно, что для восстановления нужно узнавать <tex>k</tex>-ую свободную позицию. Это можно делать с помощью [[Дерево_отрезков._Построение | дерева отрезков]] следующим образом: построим дерево отрезков для суммы на массиве из единиц. Единица в позиции означает, что данная позиция свободна. Чтобы найти <tex>k</tex>-ую свободную позицию, нужно спускаться (начиная с корня) в левое поддерево если сумма в нём больше, чем <tex>k</tex>, и в правое дерево иначе.<br />
<br />
Данный алгоритм переписывается в код следующим образом:<br />
<br />
<font color=green>// ''build_segment_tree'' {{---}} строит дерево отрезков над массивом</font><br />
<font color=green>// ''node'' {{---}} вершина дерева</font><br />
<font color=green>// ''node.index'' {{---}} индекс соответствующего элемента в массиве для листа дерева</font><br />
'''def''' recover(inv):<br />
n = inv.length<br />
tree = build_segment_tree(array(n, 1))<br />
result = array(n)<br />
curr = 1<br />
'''for''' k '''in''' inv<br />
node = tree.root<br />
'''while''' !node.is_leaf<br />
'''if''' k < node.left.value<br />
node = node.left<br />
'''else'''<br />
k -= node.left.value<br />
node = node.right<br />
result[node.index] = curr<br />
node.add(-1)<br />
curr++<br />
'''return''' result<br />
<br />
<br />
Этот алгоритм имеет сложность <tex>O(n \log n)</tex>: делается <tex>n</tex> итераций цикла, в которой происходит спуск по дереву высоты <tex>O(\log n)</tex> и один запрос на дереве отрезков. Таким образом, время работы алгоритма на каждой итерации есть <tex>O(\log n)</tex>.<br />
<br />
== Пример ==<br />
<br />
Рассмотрим пример построения таблицы инверсий и восстановления перестановки по таблице инверсий. Пусть дана перестановка <tex>(5, 7, 1, 3, 4, 6, 8, 2)</tex>. Следующая таблица показывает работу алгоритма за <tex>O(n \log n)</tex>, на каждой строке один уровень рекурсии (на первой строке — самый глубокий). В скобках стоят пары: элемент перестановки, количество инверсий. Полужирным отмечены элементы, у которых обновилось значение количества инверсий на данном шаге.<br />
<br />
{| style = "border: 0px solid; background-color: gray; text-align: center; padding : 0" cellspacing = "2"<br />
| style = "background-color: white; padding: 3px 6px" |(5, 0)<br />
| style = "background-color: white; padding: 3px 6px" |(7, 0)<br />
| style = "background-color: white; padding: 3px 6px" |(1, 0)<br />
| style = "background-color: white; padding: 3px 6px" |(3, 0)<br />
| style = "background-color: white; padding: 3px 6px" |(4, 0)<br />
| style = "background-color: white; padding: 3px 6px" |(6, 0)<br />
| style = "background-color: white; padding: 3px 6px" |(8, 0)<br />
| style = "background-color: white; padding: 3px 6px" |(2, 0)<br />
|-<br />
|colspan = "2" style = "background-color: white; padding: 3px 6px"|(5, 0), (7, 0)<br />
|colspan = "2" style = "background-color: white; padding: 3px 6px"|(1, 0), (3, 0)<br />
|colspan = "2" style = "background-color: white; padding: 3px 6px"|(4, 0), (6, 0)<br />
|colspan = "2" style = "background-color: white; padding: 3px 6px"|'''(2, 1)''', (8, 0)<br />
|-<br />
|colspan = "4" style = "background-color: white; padding: 3px 6px"|'''(1, 2)''', '''(3, 2)''', (5, 0), (7, 0)<br />
|colspan = "4" style = "background-color: white; padding: 3px 6px"|'''(2, 3)''', (4, 0), (6, 0), (8, 0)<br />
|-<br />
|colspan = "8" style = "background-color: white; padding: 3px 6px"|(1, 2), '''(2, 6)''', (3, 2), '''(4, 2)''', (5, 0), '''(6, 1)''', (7, 0), (8, 0)<br />
|}<br />
<br />
Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0, 1, 0, 0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива.<br />
<br />
{| style = "border: 0px solid; background-color: grey; text-align: center; padding : 0;" cellspacing = "2"<br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{1}</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем две свободных позиции и ставим <tex>\bf{1}</tex><br />
|-<br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{2}</tex><br />
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем шесть свободных позиций и ставим <tex>\bf{2}</tex><br />
|-<br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{3}</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex><br />
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем две свободных позиции и ставим <tex>\bf{3}</tex><br />
|-<br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{4}</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex><br />
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем две свободных позиции и ставим <tex>\bf{4}</tex><br />
|-<br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{5}</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>4</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex><br />
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|не пропускаем свободных позиции и ставим <tex>\bf{5}</tex><br />
|-<br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>4</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{6}</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex><br />
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|пропускаем одну свободную позицию и ставим <tex>\bf{6}</tex><br />
|-<br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{7}</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>4</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>6</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex><br />
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|не пропускаем свободных позиций и ставим <tex>\bf{7}</tex><br />
|-<br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>7</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>1</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>3</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>4</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>6</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{8}</tex><br />
|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>2</tex><br />
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|не пропускаем свободных позиций и ставим <tex>\bf{8}</tex><br />
|}<br />
<br />
== См. также ==<br />
* [[Матричное представление перестановок]]<br />
<br />
== Источники информации ==<br />
<br />
* [https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation]<br />
* Д. Кнут - Искусство программирования, том 3 {{---}} 29-31 с.<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Комбинаторика ]]</div>
109.187.33.19