1632
правки
Изменения
м
<tex>\mathtt{T}[1..n]\ =</tex> <tex>0</tex> '''for''' <tex>i\ =</tex> <tex>1..n</tex> '''for''' <tex>j\ =</tex> <tex>1..(i - 1)</tex> '''if''' <tex>\mathtt{P}[j]</tex> <tex>></tex> <tex>\mathtt{P}[i]</tex> <tex>\mathtt{T}[\mathtt{P}[i]]\ =</tex> <tex>\mathtt{T}[\mathtt{P}[i]]++</tex>
<tex>j++</tex> <tex>curr++</tex> '''return''' <tex>\mathtt{result}</tex>
rollbackEdits.php mass rollback
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.
Алгоритм построения в псевдокоде выглядит так:
Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Сортировка_слиянием |сортировку слиянием.]]
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично [[Сортировка_слиянием |сортировке слиянием.]]
Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количество нерассмотренных элементов второго первого списка.
Описанный алгоритм записывается в псевдокод следующим образом:
<font color=green>// <tex>inverses\_merge</tex> ''inverses_merge'' {{---}} процедура, сливающая два списка пар</font> <font color=green>// <tex>inverses\_get</tex> ''inverses_get'' {{---}} процедура, рекурсивно получающая таблицу инверсий для перестановки</font> '''def''' <tex>\mathtt{inverses\_mergeinverses_merge(ls1, ls2)}:</tex> <tex>\mathtt{result}\ = [ ]</tex> <tex>it\textit{1}it1, it\textit{2}\ it2 =</tex> ''null'' '''while''' <tex>(it\textit{1}</tex> it1 <tex><</tex> <tex>\mathtt{ls1.length})</tex> '''and''' <tex>(it\textit{2}</tex> it2 <tex><</tex> <tex>\mathtt{ls2.length}):</tex> '''if''' <tex>\mathtt{ls1}[it\textit{1}it1]\mathtt{.item}</tex> <tex><</tex> <tex>\mathtt{ls2}[it\textit{2}it2]\mathtt{.item}:</tex> <tex>\mathtt{result.append}(\mathtt{ls1}[it\textit{1}it1])</tex> <tex>it\textit{1}it1++</tex> '''else:''' <tex>\mathtt{result.append}(item\ =</tex> <tex>\mathtt{ls2}[it\textit{2}it2]\mathtt{.item}, inverses\ =</tex> <tex>\mathtt{ls2}[it\textit{2}it2]\mathtt{.inverses}</tex> <tex>+</tex> <tex>\mathtt{ls1.length}</tex> <tex>-</tex> <tex>it\textit{1}it1)</tex> <tex>it\textit{2}it2++</tex> '''while''' it1 <tex>(it\textit{1}</tex> <tex><</tex> <tex>\mathtt{ls1.length}):</tex> <tex>\mathtt{result.append}(\mathtt{ls1}[it\textit{1}it1])</tex> <tex>it\textit{1}it1++</tex> '''while''' it2 <tex>(it\textit{2}</tex> <tex><</tex> <tex>\mathtt{ls2.length}):</tex> <tex>\mathtt{result.append}(\mathtt{ls2}[it\textit{2}it2])</tex> <tex>it\textit{2}it2++</tex> '''return''' <tex>\mathtt{result}</tex>
'''def''' <tex>\mathtt{inverses\_getinverses_get(ls)}:</tex> '''if''' <tex>\mathtt{ls.length}\ == 1:</tex> '''return''' <tex>[(item = \mathtt{ls[0]}, inverses = 0)]</tex> '''else:''' '''return''' <tex>\mathtt{inverses\_mergeinverses_merge(inverses\_getinverses_get(ls.first\_halffirst_half), inverses\_getinverses_get(ls.second\_halfsecond_half))}</tex>
Сложность представленного алгоритма есть <tex>O(n\log n)</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>// <tex>''j</tex> '' {{---}} счётчик пропущенных свободных позиций</font> <font color=green>// <tex>''k</tex> '' {{---}} количество инверсий слева для элемента curr</font> <font color=green>// <tex>''result</tex> '' {{---}} массив, в который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.</font> '''def''' <tex>\mathtt{recover\_straightrecover_straight(ls)}:</tex> <tex>n\ = \mathtt{ls.length}</tex> <tex>\mathtt{result}\ = \mathtt{array}(0, n)</tex> <tex>curr\ = 1</tex> '''for''' <tex>k \'''in \mathtt{''' ls}:</tex> <tex> j\ = 0</tex> '''for''' <tex>(i\ = 0, i < ..(n, i++- 1):</tex> '''if''' <tex>\mathtt{result}[i]\ == 0:</tex> '''if''' <tex> j\ == k:</tex> <tex>\mathtt{result}[i]\ = curr</tex>
'''break'''
'''else:'''
Данный алгоритм переписывается в код следующим образом:
<font color=green>// <tex>build_segment_tre</tex> ''build_segment_tree'' {{---}} строит дерево отрезков над массивом</font> <font color=green>// <tex>''node</tex> '' {{---}} вершина дерева</font> <font color=green>// <tex>''node.index</tex> '' {{---}} индекс соответствующего элемента в массиве для листа дерева</font> '''def''' <tex>\mathtt{recover(inv)}:</tex> <tex>n\ = \mathtt{inv.length}</tex> <tex>\mathtt{tree}\ = \mathtt{build\_segment\_tree}build_segment_tree(\mathtt{array}(n, 1))</tex> <tex>\mathtt{result}\ = \mathtt{array}(n)</tex> <tex>curr\ = 1</tex> '''for''' <tex>k \'''in \mathtt{''' inv}:</tex> <tex>\mathtt{node}\ = \mathtt{tree.root}</tex> '''while''' <tex>(!\mathtt{node.is\_leaf}):</tex>is_leaf '''if''' <tex>(k <\mathtt{node.left.value}):</tex> <tex>\mathtt{node}\ = \mathtt{node.left}</tex> '''else:''' <tex>k\ -= \mathtt{node.left.value}</tex> <tex>\mathtt{node}\ = \mathtt{node.right}</tex> <tex>\mathtt{result}[\mathtt{node.index}]\ = curr</tex> <tex>\mathtt{node.add}(-1)</tex> <tex>curr++</tex> '''return''' <tex>\mathtt{result}</tex>
== См. также ==
* [[Матричное представление перестановок]]
== Источники информации ==
* [https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation]
* Д. Кнут - Искусство программирования, том 3{{---}} 29-31 с.
