1632
правки
Изменения
м
For '''for''' i = 1..n For '''for''' j = 1..(i - 1) '''if ''' P[j] > P[i] T[P[i]] = T[P[i]] + 1+Сложность данного алгоритма {{---}} $<tex>O(n^2)$</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Дерево отрезковСортировка_слиянием |сортировку слиянием.]] == Алгоритм построения за O(N log N) == Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. ПостроениеБудем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично [[Сортировка_слиянием |дерево отрезковсортировке слиянием.]] Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количество нерассмотренных элементов первого списка. Описанный алгоритм записывается в псевдокод следующим образом: <font color=green>// ''inverses_merge'' {{---}} процедура, сливающая два списка пар</font> <font color=green>// ''inverses_get'' {{---}} процедура, рекурсивно получающая таблицу инверсий для перестановки</font> '''def''' inverses_merge(ls1, ls2): result = [] it1, it2 = ''null'' '''while''' (it1 < ls1.length) '''and''' (it2 < ls2.length) '''if''' ls1[it1].item < ls2[it2].item result.append(ls1[it1]) it1++ '''else''' result.append(item = ls2[it2].item, inverses = ls2[it2].inverses + ls1.length - it1) it2++ '''while''' it1 < ls1.length result.append(ls1[it1]) it1++ '''while''' it2 < ls2.length result.append(ls2[it2]) it2++ '''return''' result '''def''' inverses_get(ls): '''if''' ls.length == 1 '''return''' [(item = ls[0], inverses = 0)] '''else''' '''return''' inverses_merge(inverses_get(ls.first_half), inverses_get(ls.second_half))
Получим из исходной перестановки обратную и запишем её в массив $M$. Также заведём массив $S$ длиной $n$, инициализированный нулями. После обработки $i$-го элемента будем вносить значение 1 в ячейку $S[M[i]]$. Обработку начинаем с последнего элемента и двигаемся к началу. Пусть, функция $Sum(i)$ возвращает значение суммы элементов массива $S$ от 1 до $i$. Тогда $i$-й элемент таблицы инверсий находится так:
$T[i] = Sum(M[i])$
Данная формула даёт правильный ответ, так как $SСложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью [M[iДерево_отрезков._Построение | дерева отрезков.]]$ содержит единицу только в том случае, если мы уже обработали элемент, стоящий в $M[i]$-й позиции. Так как обработка идёт от больших чисел к меньшим, $Sum(M[i])$ выдаст нужное нам количество чисел, больших $i$ и стоящих в перестановке левее него.
Функция $Sum$ реализуется с помощью [[Дерево отрезков. Построение|дерева отрезков]]. Каждое изменение массива и обращение к функции $Sum$ влечёт == Алгоритм построения за собой $\log_2n$ операций. Таким образом получаем сложность алгоритма $O(n\log_2nN)$==
Также существует достаточно простой алгоритм Для построения таблицы инверсий с использованием за линейное время воспользуемся [[Сортировка слияниемКарманная сортировка |сортировки слияниемкарманной сортировкой]]. Вначале выписываются следующие упорядоченные пары чисел: в $i$-ой паре на первом месте стоит $i$-й элемент перестановки, а на втором {{---}} 0. Далее применяется При [[Сортировка слияниемКарманная сортировка |сортировка слияниемкарманной сортировке]]нужно определить карман <tex>B</tex>, при чем при выписывании элемента из второй цепочки упорядоченных пар, в который попадет текущий элемент. Затем найти число на второй позиции элементов в данном элементе увеличивается на старших карманах относительно <tex>B</tex>. Потом аккуратно подсчитать количество элементов, оставшихся больших текущего в первой цепочке. В конце сортировки получим цепочку упорядоченных паркармане <tex>B</tex>. Выписывая вторые элементы данных упорядоченных парКарман <tex>A</tex> считается старшим для кармана <tex>B</tex>, получим искомую таблицу инверсий. Сложность данного алгоритма совпадает со сложностью [[Сортировка слиянием|сортировки слиянием]] и составляет $O(n\log_2n)$если любой элемент из <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>// ищем сколько инверсий эленент создает в эту таблицу число $i$ своем кармане</font> bank[pos].insert(где $newPosition, permutation[i$ от $n$ до 1]) <font color=green>// вставляем элемент в Карман на свою позицию $k</font> '''for''' i = position +1$, где $k$ to bucket - число 1 <font color=green>// ищем сколько инверсий он создает с элементами в таблице инверсий на $других карманах</font> answer += bank[i$-том месте. Данный алгоритм довольно прост в реализации, но без использования дополнительных структур данных, имеет сложность $O(n^2)$, т. к. для вставки элемента в определённую позицию, требуется порядка $n$ перестановок элементов].size '''return''' answer
Приведём алгоритм восстановления с использованием В разделе [[Сортировка слияниемКарманная сортировка |сортировки слияниемкарманная сортировка]]доказывается, имеющий сложность $O(n\log_2n)$что она работает за линейное время. Что касается подсчета инверсий, то в приведенной реализации происходит [[Карманная сортировка | карманная сортировка]] в online режиме и вся математическая часть подходит и под этот случай.
Пусть $\alpha$ и $\beta$ - цепочки упорядоченных пар целых неотрицательных чисел $Следует отметить, что хотя подсчет с помощью [m_1, n_1]\dots[m_k, n_kКарманная сортировка | карманной сортировки]$. Рассмотрим двоичную операцию $\circ$, рекурсивно определенную на парах таких цепочек следующим образом: $([m, n]\alpha)\circ([m'выполняется за линейное время, n']\beta)=\left\{\begin{aligned}[]но имеет очень большую константу поэтому подсчет [m,n]инверсий рассматриваемый выше за <tex>O(\alpha \circ ([m'-m, n']\beta)), m \le m',\\ [m', n'](([m-m'-1, log n]\alpha) \circ \beta), m</tex>m'.\\ \end{aligned} \rightработает быстрее .$
Сопоставим каждому элементу таблицы инверсий его номер. Получится множество упорядоченных пар чисел $[m_1, n_1]\dots[m_k, n_k]$, где $m_i$ {{---}} сам элемент, а $n_i$ {{---}} его номер. Разобьём данные элементы на пары и произведём с ними операцию $\circ$. Получим некоторое количество цепочек упорядоченных пар. Также разбиваем их на пары и производим операцию $\circ$. Так действуем, пока не останется одна цепочка. Выписывая вторые элементы данных упорядоченных пар в том порядке, в каком они представлены в цепочке, получим первоначальную перестановку.== Алгоритм восстановления ==
Цепочка наподобие $[4Для восстановления перестановки по таблицы инверсий <tex>T</tex> воспользуемся следующим соображением: единица стоит в перестановке на <tex>T_0</tex>-ом месте (индексируем элементы с нуля), так как остальные числа в перестановке больше единицы. Далее, 4][если известны расположения всех чисел <tex>1,3]$ представляет "_ _ _ _ 4 _ 3 _ $\infty$"dots, k</tex>, где "_" означает пропускто число <tex>k + 1</tex> стоит на <tex>T_{k + 1}</tex>-ой ещё не занятой позиции: все числа, меньшие <tex>k + 1</tex> уже расставлены. Операция $\alpha \circ \beta$ вставляет пропуски и заполнения из $\beta$ на место пропусков Это рассуждение напрямую переписывается в код следующим образом: <font color=green>// ''j'' {{---}} счётчик пропущенных свободных позиций</font> <font color=green>// ''k'' {{---}} количество инверсий слева для элемента curr</font> <font color=green>// ''result'' {{---}} массив, в $\alpha$который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.</font> '''def''' recover_straight(ls): n = ls.length result = array(0, n) curr = 1 '''for''' k '''in''' ls j = 0 '''for''' i = 0..(n - 1) '''if''' result[i] == 0 '''if''' j == k result[i] = curr '''break''' '''else:''' j++ curr++ '''return''' result
== Пример ==
* $[4Этот простой алгоритм имеет сложность <tex>O(n^2)</tex> — внутренний цикл делает до <tex>n</tex> итераций, 1внешний — ровно <tex>n</tex> итераций. Видно, 6что для восстановления нужно узнавать <tex>k</tex>-ую свободную позицию. Это можно делать с помощью [[Дерево_отрезков._Построение | дерева отрезков]] следующим образом: построим дерево отрезков для суммы на массиве из единиц. Единица в позиции означает, 3, 2, 2что данная позиция свободна. Чтобы найти <tex>k</tex>-ую свободную позицию, 1нужно спускаться (начиная с корня) в левое поддерево если сумма в нём больше, 1чем <tex>k</tex>, 1, 0]$ - таблица инверсийи в правое дерево иначе. Данный алгоритм переписывается в код следующим образом:
* $[4,1]\circ[1,2], [6,3]\circ[3,4], [2,5]\circ[2,6], [1,7]\circ[1,8], [1,9]\circ[0,10]$
* $[1,2][2,1]\circ[3,4][2,3], [2,5][0,6]\circ[1,7][0,8], [0,10][0,9]$== Пример ==
* $[{| style = "border: 0px solid; background-color: gray; text-align: center; padding : 0" cellspacing = "2"| 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]\circ[1,2)''', (5, 0), (7][, 0)|colspan = "4" style = "background-color: white; padding: 3px 6px"|'''(2, 3)''', (4,5][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,10][0), (8,9]$0)|}
* $[{| style = "border: 0px solid; 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>|colspan = "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,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>\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][0," 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,6][</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,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{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>\circ[bf{6}</tex>|colspan = "1" style = "background-color: white; padding: 3px 6px"|<tex>0,10][</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,9]$</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>|}
* $[0,10][0,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3][0,9]$== Источники информации ==
Получаем перестановку $[10, 2, 7, 5, 1, 4, 6, 8, 3, 9]$
= Источники =[[Категория: Дискретная математика и алгоритмы]]
* Д. Кнут - Искусство программирования, том 3.</wikitex>[[Категория: Комбинаторика ]]
rollbackEdits.php mass rollback
Пусть <wikitextex>Пусть $ P = (p_1,p_2,\dots,p_n)$ </tex> является [[Действие перестановки на набор из элементов, представление в виде циклов|перестановкой]] чисел $ <tex> 1, 2,\dots, n$</tex>.
{{Определение
|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>) ==
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.
Алгоритм построения в псевдокоде выглядит так:
T[1..n] = 0
<font color=green>// ''build_segment_tree'' {{---}} строит дерево отрезков над массивом</font>
<font color=green>// ''node'' {{---}} вершина дерева</font>
<font color=green>// ''node.index'' {{---}} индекс соответствующего элемента в массиве для листа дерева</font>
'''def''' recover(inv):
n = inv.length
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++
'''return''' result
Этот алгоритм имеет сложность <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>, на каждой строке один уровень рекурсии (на первой строке — самый глубокий). В скобках стоят пары: элемент перестановки, количество инверсий. Полужирным отмечены элементы, у которых обновилось значение количества инверсий на данном шаге.
Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0, 1, 0, 0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива.
== См. также ==
* [[Матричное представление перестановок]]
* [https://en.wikipedia.org/wiki/Permutation Wikipedia {{---}} Permutation]
* Д. Кнут - Искусство программирования, том 3 {{---}} 29-31 с.
