25
правок
Изменения
Нет описания правки
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.
Алгоритм построения в псевдокоде выглядит так:
Сложность данного алгоритма {{---}} <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}it1 </tex> <tex><</tex> <tex>\mathtt{ls1.length})</tex> '''and''' <tex>(it\textit{2}</tex> <tex><</tex> it2 <tex>\mathtt{ls2.length}):</tex> '''if''' <tex>\mathtt{ls1}[it\textit{1it1}]\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:'''
'''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>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\ =</tex> <tex>0</tex> '''for''' <tex>(i\ = 0, i < ..n, i++):</tex> '''if''' <tex>\mathtt{result}[i]\ ==</tex> <tex>0:</tex> '''if''' <tex> j\ ==</tex> <tex>k:</tex> <tex>\mathtt{result}[i]\ =</tex> <tex>curr</tex>
'''break'''
'''else:'''
Данный алгоритм переписывается в код следующим образом:
<font color=green>// <tex>build\_segment\_tree</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:'''
