25
правок
Изменения
Нет описания правки
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.
Алгоритм построения в псевдокоде выглядит так:
<tex>\mathtt{T}[1..n] \ = </tex> <tex>0</tex> For '''for''' <tex>i \ = </tex> <tex>1..n</tex> For '''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]] + 1+</tex>
Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Сортировка_слиянием |сортировку слиянием.]]
'''def''' <tex>\mathtt{recover(inv)}:</tex>
<tex>n\ = \mathtt{inv.length}</tex>
<tex>\mathtt{tree}\ = \mathtt{build_segment_treebuild\_segment\_tree}(\mathtt{array}(n, 1))</tex>
<tex>\mathtt{result}\ = \mathtt{array}(n)</tex>
<tex>curr\ = 1</tex>
|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"|не пропускаем свободных позиций и ставим <tex>\bf{8}</tex>
|}
== См. также ==
* [[Матричное представление перестановок]]
== Источники информации ==
* [https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation]
* Д. Кнут - Искусство программирования, том 3.
