Изменения

Перейти к: навигация, поиск

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

8090 байт добавлено, 18:48, 12 января 2015
Нет описания правки
{{Определение
|definition =
'''Инверсией''' (англ. ''inversion'') в перестановке <tex>P</tex> называется всякая пара индексов <tex>i, j</tex> такая, что <tex>1\leqslant i<j\leqslant n</tex> и <tex>P[i]>P[j]</tex>.
}}
{{Определение
|definition =
'''Таблицей инверсий''' (англ. ''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>.
}}
== Алгоритм построения за O(N<sup>2</sup>) ==
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.
if P[j] > P[i]
T[P[i]] = T[P[i]] + 1
Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Сортировка_слиянием |сортировку слиянием. ]]
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично сортировке слиянием.== Алгоритм построения за O(N log N) ==
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично [[Сортировка_слиянием |сортировке слиянием.]] Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количетво количество нерассмотренных элементов второго списка.
Описанный алгоритм записывается в псевдокод следующим образом:
<font color=green>// <tex>inverses\_merge</tex> {{---}} процедура, сливающая два списка пар</font> <font color=green>// <tex>inverses\_get</tex> {{---}} процедура, рекурсивно получающая таблицу инверсий для перестановки</font> '''def inverses_merge''' <tex>\mathtt{inverses\_merge(ls1, ls2)}:</tex> <tex>\mathtt{result }\ = [ ]</tex> it1<tex>it\textit{1}, it2 it\textit{2}\ = 0, 0</tex> ''null'' '''while ''' <tex>(it1 it\textit{1}</tex> <tex><</tex> < len(tex>\mathtt{ls1.length})) </tex> '''and ''' <tex>(it2 it\textit{2}</tex> <tex><</tex> < len(tex>\mathtt{ls2).length}):</tex> '''if ''' <tex>\mathtt{ls1}[it1it\textit{1}]\mathtt{.item }</tex> <tex><</tex> < tex>\mathtt{ls2}[it2it\textit{2}]\mathtt{.item}:</tex> <tex>\mathtt{result.append}(\mathtt{ls1}[it1it\textit{1}])</tex> it1 <tex>it\textit{1}+= 1+</tex> '''else:''' <tex>\mathtt{result.append}(item \ = </tex> <tex>\mathtt{ls2}[it2it\textit{2}]\mathtt{.item}, inverses \ = </tex> <tex>\mathtt{ls2}[it2it\textit{2}]\mathtt{.inverses }</tex> <tex>+ len(</tex> <tex>\mathtt{ls1) .length}</tex> <tex>- it1</tex> <tex>it\textit{1})</tex> it2 <tex>it\textit{2}++= 1</tex> '''while ''' <tex>(it1 it\textit{1}</tex> <tex>< len(</tex> <tex>\mathtt{ls1).length}):</tex> <tex>\mathtt{result.append}(\mathtt{ls1}[it1it\textit{1}])</tex> it1 <tex>it\textit{1}++= 1</tex> '''while ''' <tex>(it2 it\textit{2}</tex> <tex><</tex> < len(tex>\mathtt{ls2).length}):</tex> <tex>\mathtt{result.append}(\mathtt{ls2}[it2it\textit{2}])</tex> it2 <tex>it\textit{2}++= 1</tex> '''return ''' <tex>\mathtt{result}</tex>
'''def inverses_get''' <tex>\mathtt{inverses\_get(ls)}:</tex> '''if len(''' <tex>\mathtt{ls) .length}\ == 1:</tex> '''return ''' <tex>[(item = \mathtt{ls[0]}, inverses = 0)]</tex> '''else:''' '''return inverses_merge''' <tex>\mathtt{inverses\_merge(inverses_getinverses\_get(ls.first_halffirst\_half), inverses_getinverses\_get(ls.second_halfsecond\_half))}</tex>
* inverses_merge — процедура, сливающая два списка пар
* inverses_get — процедура, рекурсивно получающая таблицу инверсий для перестановки
Сложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью [[Дерево_отрезков._Построение | дерева отрезков.]]
== Алгоритм восстановления ==
Для восстановления перестановки по таблицы инверсий <tex>T</tex> воспользуемся следующим соображением: единица стоит в перестановке на <tex>T_iT_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\_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++):</tex> '''if''' <tex>\mathtt{result}[i]\ == 0:</tex> '''if''' <tex>j\ == k:</tex> <tex>\mathtt{result}[i]\ = curr</tex> '''break''' '''else:''' <tex>j++</tex> <tex>curr++</tex> '''return''' <tex>\mathtt{result}</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>, и в правое дерево иначе.
Данный алгоритм переписывается в код следующим образом:
<font color=green>// <tex>build_segment_tre</tex> {{---}} строит дерево отрезков над массивом</font> <font color=green>// <tex>node</tex> {{---}} вершина дерева</font> <font color=green>// <tex>node.index</tex> {{---}} индекс соответствующего элемента в массиве для листа дерева</font> '''def ''' <tex>\mathtt{recover(inv)}:</tex> <tex>n \ = len(\mathtt{inv).length}</tex> <tex>\mathtt{tree }\ = \mathtt{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_leafis\_leaf}):</tex> '''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 += 1+</tex> '''return ''' <tex>\mathtt{result}</tex>
* 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 = "12"
| style = "background-color: white; padding: 3px 6px" |(5, 0)
| style = "background-color: white; padding: 3px 6px" |(7, 0)
Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0, 1, 0, 0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива.
{| cellpadding = "3" style = "border: 1px 0px solid gray; background-color: grey; text-align: center; padding : 0;" cellspacing = "2"| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>| '''colspan = "1''' " style = "background-color: white; padding: 3px 6px"|<tex>\bf{1}</tex>| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>| &nbspcolspan = "1" style = "background-color: #EEF; text-align: left; |padding: 3px 6px"|пропускаем две свободных позиции и ставим <tex>\bf{1}</tex>
|-
| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>1 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| '''<tex>\bf{2''' || }</tex>|colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"| пропускаем шесть свободных позиций и ставим <tex>\bf{2}</tex>
|-
| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>1 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| '''<tex>\bf{3''' }</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>2 </tex>|| |colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"| пропускаем две свободных позиции и ставим <tex>\bf{3}</tex>
|-
| _ colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>1 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>3 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| '''<tex>\bf{4''' }</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>2 </tex>|| |colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"| пропускаем две свободных позиции и ставим <tex>\bf{4}</tex>
|-
| '''colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>\bf{5''' }</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>1 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>3 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>4 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>2 </tex>|| |colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"| не пропускаем свободных позиции и ставим <tex>\bf{5}</tex>
|-
| colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>1 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>3 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>4 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| '''<tex>\bf{6''' }</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>2 </tex>|| |colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"| пропускаем одну свободную позицию и ставим <tex>\bf{6}</tex>
|-
| colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| '''<tex>\bf{7''' }</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>1 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>3 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>4 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>6 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| _ <tex>0</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>2 </tex>|| |colspan = "1" style = "background-color: #EEF; text-align: left; padding: 3px 6px"| не пропускаем свободных позиций и ставим <tex>\bf{7}</tex>
|-
| colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>5 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>7 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>1 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>3 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>4 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>6 </tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| '''<tex>\bf{8''' }</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"| <tex>2 </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.
 
== См. также ==
* [[Матричное представление перестановок]]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
6yry6e
25
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/44306»

Навигация