Таблица инверсий

2013-09-17T12:55:55Z

Dans: Необходимо сравнивать со значением в левом поддереве

Пусть <tex> P = (p_1,p_2,\dots,p_n)</tex> является [[Действие перестановки на набор из элементов, представление в виде циклов|перестановкой]] чисел <tex> 1, 2,\dots, n</tex>.

{{Определение
|definition =
'''Инверсией''' в перестановке <tex>P</tex> называется всякая пара индексов <tex>i, j</tex> такая, что <tex>1\leqslant i<j\leqslant n</tex> и <tex>P[i]>P[j]</tex>.
}}
{{Определение
|definition =
'''Таблицей инверсий''' перестановки <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>.
}}

== Алгоритм построения ==

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

Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично сортировке слиянием.

Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количетво нерассмотренных элементов второго списка.

Описанный алгоритм записывается в псевдокод следующим образом:

def inverses_merge(ls1, ls2):
result = []
it1, it2 = 0, 0
while (it1 < len(ls1)) and (it2 < len(ls2)):
if ls1[it1].item < ls2[it2].item:
result.append(ls1[it1])
it1 += 1
else:
result.append(item = ls2[it2].item, inverses = ls2[it2].inverses + len(ls1) - it1)
it2 += 1
while (it1 < len(ls1)):
result.append(ls1[it1])
it1 += 1
while (it2 < len(ls2)):
result.append(ls2[it2])
it2 += 1
return result

def inverses_get(ls):
if len(ls) == 1:
return [(item = ls[0], inverses = 0)]
else:
return inverses_merge(inverses_get(ls.first_half), inverses_get(ls.second_half))

* inverses_merge — процедура, сливающая два списка пар
* inverses_get — процедура, рекурсивно получающая таблицу инверсий для перестановки

Сложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью дерева отрезков.

== Алгоритм восстановления ==

Для восстановления перестановки по таблицы инверсий <tex>T</tex> воспользуемся следующим соображением: единица стоит на <tex>T_i</tex>-ом месте (индексируем элементы с нуля), так как остальные числа в перестановке больше единицы. Далее, если известны расположения всех чисел <tex>1, \dots, k</tex>, то число <tex>k + 1</tex> стоит на <tex>T_{k + 1}</tex>-ой ещё не занятой позиции: все числа, меньшие <tex>k + 1</tex> уже расставлены. Это рассуждение напрямую переписывается в код следующим образом:

def recover_straight(ls):
n = len(ls)
result = array(0, n)
curr = 1
for k in ls:
j = 0
for (i = 0, i < n, i += 1):
if result[i] == 0:
if j == k:
result[i] = curr
break
else:
j += 1
curr += 1
return result

* j — счётчик пропущенных свободных позиций
* k — количество инверсий слева для элемента curr
* result — массив, в который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.

Этот простой алгоритм имеет сложность <tex>O(n^2)</tex> — внутренний цикл делает до <tex>n</tex> итераций, внешний — ровно <tex>n</tex> итераций.

Видно, что для восстановления нужно узнавать <tex>k</tex>-ую свободную позицию. Это можно делать с помощью дерева отрезков следующим образом: построим дерево отрезков для суммы на массиве из единиц. Единица в позиции означает, что данная позиция свободна. Чтобы найти <tex>k</tex>-ую свободную позицию, нужно спускаться (начиная с корня) в левое поддерево если сумма в нём больше, чем <tex>k</tex>, и в правое дерево иначе.

Данный алгоритм переписывается в код следующим образом:

def recover(inv):
n = len(inv)
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 += 1
return result

* build_segment_tree — строит дерево отрезков над массивом
* node — вершина дерева
* node.index — индекс соответсвующего элемента в массиве для листа дерева

Этот алгоритм имеет сложность <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>, на каждой строке один уровень рекурсии (на первой строке — самый глубокий). В скобках стоят пары: элемент перестановки, количество инверсий. Полужирным отмечены элементы, у которых обновилось значение количества инверсий на данном шаге.

{| style = "border: 0px solid; background-color: gray; text-align: center; padding : 0" cellspacing = "1"
| 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 = "background-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" |(2, 0)
|-
|colspan = "2" style = "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" style = "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 = "background-color: white; padding: 3px 6px"|'''(2, 3)''', (4, 0), (6, 0), (8, 0)
|-
|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)
|}

Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0, 1, 0, 0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива.

{| cellpadding = "3" style = "border: 1px solid gray"
| _ || _ || '''1''' || _ || _ || _ || _ || _ ||   ||пропускаем две свободных позиции и ставим 1
|-
| _ || _ || 1 || _ || _ || _ || _ || '''2''' || || пропускаем шесть свободных позиций и ставим 2
|-
| _ || _ || 1 || '''3''' || _ || _ || _ || 2 || || пропускаем две свободных позиции и ставим 3
|-
| _ || _ || 1 || 3 || '''4''' || _ || _ || 2 || || пропускаем две свободных позиции и ставим 4
|-
| '''5''' || _ || 1 || 3 || 4 || _ || _ || 2 || || не пропускаем свободных позиции и ставим 5
|-
| 5 || _ || 1 || 3 || 4 || '''6''' || _ || 2 || || пропускаем одну свободную позицию и ставим 6
|-
| 5 || '''7''' || 1 || 3 || 4 || 6 || _ || 2 || || не пропускаем свободных позиций и ставим 7
|-
| 5 || 7 || 1 || 3 || 4 || 6 || '''8''' || 2 || || не пропускаем свободных позиций и ставим 8
|}

== Источники ==

* Д. Кнут - Искусство программирования, том 3.

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

Викиконспекты - Вклад участника [ru]

Таблица инверсий