Таблица инверсий — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Необходимо сравнивать со значением в левом поддереве)
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 10 участников)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Инверсией''' в перестановке <tex>P</tex> называется всякая пара индексов <tex>i, j</tex> такая, что <tex>1\leqslant i<j\leqslant n</tex> и <tex>P[i]>P[j]</tex>.
+
'''Инверсией''' (англ. ''inversion'') в перестановке <tex>P</tex> называется всякая пара индексов <tex>i, j</tex> такая, что <tex>1\leqslant i<j\leqslant n</tex> и <tex>P[i]>P[j]</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =  
 
|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>.
+
'''Таблицей инверсий''' (англ. ''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
 
  T[1..n] = 0
  For i = 1..n
+
  '''for''' i = 1..n
   For j = 1..(i - 1)
+
   '''for''' j = 1..(i - 1)
     if P[j] > P[i]
+
     '''if''' P[j] > P[i]
       T[P[i]] = T[P[i]] + 1
+
       T[P[i]] = T[P[i]]++
Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на сортировку слиянием.  
+
Сложность данного алгоритма {{---}} <tex>O(n^2)</tex>. Уменьшить время работы можно используя алгоритм, похожий на [[Сортировка_слиянием |сортировку слиянием.]]
  
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично сортировке слиянием.
+
== Алгоритм построения за O(N log N) ==
  
Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количетво нерассмотренных элементов второго списка.
+
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично [[Сортировка_слиянием |сортировке слиянием.]]
 +
 
 +
Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количество нерассмотренных элементов первого списка.
  
 
Описанный алгоритм записывается в псевдокод следующим образом:
 
Описанный алгоритм записывается в псевдокод следующим образом:
 
+
<font color=green>// ''inverses_merge'' {{---}} процедура, сливающая два списка пар</font>
  def inverses_merge(ls1, ls2):
+
<font color=green>// ''inverses_get'' {{---}} процедура, рекурсивно получающая таблицу инверсий для перестановки</font>
 +
  '''def''' inverses_merge(ls1, ls2):
 
   result = []
 
   result = []
   it1, it2 = 0, 0
+
   it1, it2 = ''null''
   while (it1 < len(ls1)) and (it2 < len(ls2)):
+
   '''while''' (it1 < ls1.length) '''and''' (it2 < ls2.length)
    if ls1[it1].item < ls2[it2].item:
+
    '''if''' ls1[it1].item < ls2[it2].item
 
       result.append(ls1[it1])
 
       result.append(ls1[it1])
       it1 += 1
+
       it1++
     else:
+
     '''else'''
       result.append(item = ls2[it2].item, inverses = ls2[it2].inverses + len(ls1) - it1)
+
       result.append(item = ls2[it2].item, inverses = ls2[it2].inverses + ls1.length - it1)
       it2 += 1
+
       it2++
   while (it1 < len(ls1)):
+
   '''while''' it1 < ls1.length
 
     result.append(ls1[it1])
 
     result.append(ls1[it1])
     it1 += 1
+
     it1++
   while (it2 < len(ls2)):
+
   '''while''' it2 < ls2.length
 
     result.append(ls2[it2])
 
     result.append(ls2[it2])
     it2 += 1
+
     it2++
   return result
+
   '''return''' result
 
   
 
   
  def inverses_get(ls):
+
  '''def''' inverses_get(ls):
   if len(ls) == 1:
+
   '''if''' ls.length == 1
     return [(item = ls[0], inverses = 0)]
+
     '''return''' [(item = ls[0], inverses = 0)]
   else:
+
   '''else'''
     return inverses_merge(inverses_get(ls.first_half), inverses_get(ls.second_half))
+
     '''return''' inverses_merge(inverses_get(ls.first_half), inverses_get(ls.second_half))
 +
 
 +
 
 +
Сложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью [[Дерево_отрезков._Построение | дерева отрезков.]]
  
* inverses_merge — процедура, сливающая два списка пар
+
== Алгоритм построения за O(N) ==
* inverses_get — процедура, рекурсивно получающая таблицу инверсий для перестановки
 
  
Сложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью дерева отрезков.
+
Для построения таблицы инверсий за линейное время воспользуемся [[Карманная сортировка | карманной сортировкой]]. При [[Карманная сортировка | карманной сортировке]] нужно определить карман <tex>B</tex>, в который попадет текущий элемент. Затем найти число элементов в старших карманах относительно <tex>B</tex>. Потом аккуратно подсчитать количество элементов, больших текущего в кармане <tex>B</tex>. Карман <tex>A</tex> считается старшим для кармана <tex>B</tex>, если любой элемент из <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>// ищем сколько инверсий эленент создает в своем кармане</font>
 +
      bank[pos].insert(newPosition, permutation[i]) <font color=green>// вставляем элемент в Карман на свою позицию </font>
 +
      '''for''' i = position + 1 to bucket - 1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font>
 +
        answer += bank[i].size
 +
    '''return''' answer
 +
 
 +
В разделе [[Карманная сортировка | карманная сортировка]] доказывается, что она работает за линейное время. Что касается подсчета инверсий, то  в приведенной реализации происходит [[Карманная сортировка | карманная сортировка]] в online режиме и вся математическая часть подходит и под этот случай.
 +
 
 +
Следует отметить, что хотя подсчет с помощью [[Карманная сортировка | карманной сортировки]] выполняется за линейное время, но имеет очень большую константу поэтому подсчет  инверсий рассматриваемый выше за <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> уже расставлены. Это рассуждение напрямую переписывается в код следующим образом:
+
Для восстановления перестановки по таблицы инверсий <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>// ''j'' {{---}} счётчик пропущенных свободных позиций</font>
  def recover_straight(ls):
+
<font color=green>// ''k'' {{---}} количество инверсий слева для элемента curr</font>
   n = len(ls)
+
<font color=green>// ''result'' {{---}} массив, в который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.</font>
 +
  '''def''' recover_straight(ls):
 +
   n = ls.length
 
   result = array(0, n)
 
   result = array(0, n)
 
   curr = 1
 
   curr = 1
   for k in ls:
+
   '''for''' k '''in''' ls
    j = 0
+
    j = 0
     for (i = 0, i < n, i += 1):
+
     '''for''' i = 0..(n - 1)
       if result[i] == 0:
+
       '''if''' result[i] == 0
         if j == k:
+
         '''if'''  j == k
 
           result[i] = curr
 
           result[i] = curr
           break
+
           '''break'''
         else:
+
         '''else:'''
           j += 1
+
           j++
     curr += 1
+
     curr++
   return result
+
   '''return''' result
  
* j — счётчик пропущенных свободных позиций
 
* k — количество инверсий слева для элемента curr
 
* result — массив, в который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.
 
  
 
Этот простой алгоритм имеет сложность <tex>O(n^2)</tex> — внутренний цикл делает до <tex>n</tex> итераций, внешний — ровно <tex>n</tex> итераций.
 
Этот простой алгоритм имеет сложность <tex>O(n^2)</tex> — внутренний цикл делает до <tex>n</tex> итераций, внешний — ровно <tex>n</tex> итераций.
  
Видно, что для восстановления нужно узнавать <tex>k</tex>-ую свободную позицию. Это можно делать с помощью дерева отрезков следующим образом: построим дерево отрезков для суммы на массиве из единиц. Единица в позиции означает, что данная позиция свободна. Чтобы найти <tex>k</tex>-ую свободную позицию, нужно спускаться (начиная с корня) в левое поддерево если сумма в нём больше, чем <tex>k</tex>, и в правое дерево иначе.
+
Видно, что для восстановления нужно узнавать <tex>k</tex>-ую свободную позицию. Это можно делать с помощью [[Дерево_отрезков._Построение | дерева отрезков]] следующим образом: построим дерево отрезков для суммы на массиве из единиц. Единица в позиции означает, что данная позиция свободна. Чтобы найти <tex>k</tex>-ую свободную позицию, нужно спускаться (начиная с корня) в левое поддерево если сумма в нём больше, чем <tex>k</tex>, и в правое дерево иначе.
  
 
Данный алгоритм переписывается в код следующим образом:
 
Данный алгоритм переписывается в код следующим образом:
  
  def recover(inv):
+
  <font color=green>// ''build_segment_tree'' {{---}} строит дерево отрезков над массивом</font>
   n = len(inv)
+
<font color=green>// ''node'' {{---}} вершина дерева</font>
 +
<font color=green>// ''node.index'' {{---}} индекс соответствующего элемента в массиве для листа дерева</font>
 +
'''def''' recover(inv):
 +
   n = inv.length
 
   tree = build_segment_tree(array(n, 1))
 
   tree = build_segment_tree(array(n, 1))
 
   result = array(n)
 
   result = array(n)
 
   curr = 1
 
   curr = 1
   for k in inv:
+
   '''for''' k '''in''' inv
 
     node = tree.root
 
     node = tree.root
     while (!node.is_leaf):
+
     '''while''' !node.is_leaf
       if (k < node.left.value):
+
       '''if''' k < node.left.value
 
         node = node.left
 
         node = node.left
       else:
+
       '''else'''
 
         k -= node.left.value
 
         k -= node.left.value
 
         node = node.right
 
         node = node.right
 
     result[node.index] = curr
 
     result[node.index] = curr
 
     node.add(-1)
 
     node.add(-1)
     curr += 1
+
     curr++
   return result
+
   '''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>O(n \log n)</tex>: делается <tex>n</tex> итераций цикла, в которой происходит спуск по дереву высоты <tex>O(\log n)</tex> и один запрос на дереве отрезков. Таким образом, время работы алгоритма на каждой итерации есть <tex>O(\log n)</tex>.
Строка 114: Строка 140:
 
Рассмотрим пример построения таблицы инверсий и восстановления перестановки по таблице инверсий. Пусть дана перестановка <tex>(5, 7, 1, 3, 4, 6, 8, 2)</tex>. Следующая таблица показывает работу алгоритма за <tex>O(n \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 = "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" |(5, 0)
 
| style = "background-color: white; padding: 3px 6px" |(7, 0)
 
| style = "background-color: white; padding: 3px 6px" |(7, 0)
Строка 137: Строка 163:
 
Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0, 1, 0, 0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива.
 
Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0, 1, 0, 0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива.
  
{| cellpadding = "3" style = "border: 1px solid gray"
+
{| style = "border: 0px solid; background-color: grey; text-align: center; padding : 0;" cellspacing = "2"
| _ || _ || '''1''' || _ || _ || _ || _ || _ || &nbsp; ||пропускаем две свободных позиции и ставим 1
+
|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>
 
|-
 
|-
| _ || _ || 1 || _ || _ || _ || _ || '''2''' || || пропускаем шесть свободных позиций и ставим 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>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>
 
|-
 
|-
| _ || _ || 1 || '''3''' || _ || _ || _ || 2 || || пропускаем две свободных позиции и ставим 3
+
|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>
 
|-
 
|-
| _ || _ || 1 || 3 || '''4''' || _ || _ || 2 || || пропускаем две свободных позиции и ставим 4
+
|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>
 
|-
 
|-
| '''5''' || _ || 1 || 3 || 4 || _ || || 2 || || не пропускаем свободных позиции и ставим 5
+
|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>
 
|-
 
|-
| 5 || _ || 1 || 3 || 4 || '''6''' || || 2 || || пропускаем одну свободную позицию и ставим 6
+
|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>
 
|-
 
|-
| 5 || '''7''' || 1 || 3 || 4 || 6 || _ || 2 || || не пропускаем свободных позиций и ставим 7
+
|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>
 
|-
 
|-
| 5 || 7 || 1 || 3 || 4 || 6 || '''8''' || 2 || || не пропускаем свободных позиций и ставим 8
+
|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 {{---}} 29-31 с.
  
* Д. Кнут - Искусство программирования, том 3.
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Текущая версия на 19:18, 4 сентября 2022

Пусть [math] P = (p_1,p_2,\dots,p_n)[/math] является перестановкой чисел [math] 1, 2,\dots, n[/math].


Определение:
Инверсией (англ. inversion) в перестановке [math]P[/math] называется всякая пара индексов [math]i, j[/math] такая, что [math]1\leqslant i\lt j\leqslant n[/math] и [math]P[i]\gt P[j][/math].


Определение:
Таблицей инверсий (англ. inversion table) перестановки [math] P [/math] называют такую последовательность [math] T = (t_1,t_2,\dots,t_n)[/math], в которой [math]t_i[/math] равно числу элементов перестановки [math] P [/math], стоящих в [math] P [/math] левее числа [math]i[/math] и больших [math]i[/math].


Алгоритм построения за O(N2)

Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него. Алгоритм построения в псевдокоде выглядит так:

T[1..n] = 0
for i = 1..n
  for j = 1..(i - 1)
    if P[j] > P[i]
      T[P[i]] = T[P[i]]++

Сложность данного алгоритма — [math]O(n^2)[/math]. Уменьшить время работы можно используя алгоритм, похожий на сортировку слиянием.

Алгоритм построения за O(N log N)

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

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

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

// inverses_merge — процедура, сливающая два списка пар
// inverses_get — процедура, рекурсивно получающая таблицу инверсий для перестановки
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))


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

Алгоритм построения за O(N)

Для построения таблицы инверсий за линейное время воспользуемся карманной сортировкой. При карманной сортировке нужно определить карман [math]B[/math], в который попадет текущий элемент. Затем найти число элементов в старших карманах относительно [math]B[/math]. Потом аккуратно подсчитать количество элементов, больших текущего в кармане [math]B[/math]. Карман [math]A[/math] считается старшим для кармана [math]B[/math], если любой элемент из [math]A[/math] больше любого элемента из [math]B[/math].


int bucket_sort(vector<int> permutation):
   int max = число больше permutation.size и из которого можно извлечь целый квадратный корень
   int bucket = sqrt(max)
   int answer = 0 // изначально кол-во инверсий
   list<list<int>> bank(bucket)
   for i = 0 to permutation.size 
     int pos = (permutation[i] - 1) / (max / bucket) // Определяем в каком кармане должен лежать элемент
     int newPosition = 0
     while newPosition < bank[pos].size and bank[pos][newPosition] < permutation[i] // идем до позиции где должен стоять элемент permutation[i]  
        newPosition++
     answer += bank[pos].size - newPosition // ищем сколько инверсий эленент создает в своем кармане
     bank[pos].insert(newPosition, permutation[i]) // вставляем элемент в Карман на свою позицию 
     for i = position + 1 to bucket - 1 // ищем сколько инверсий он создает с элементами в других карманах
       answer += bank[i].size
   return answer

В разделе карманная сортировка доказывается, что она работает за линейное время. Что касается подсчета инверсий, то в приведенной реализации происходит карманная сортировка в online режиме и вся математическая часть подходит и под этот случай.

Следует отметить, что хотя подсчет с помощью карманной сортировки выполняется за линейное время, но имеет очень большую константу поэтому подсчет инверсий рассматриваемый выше за [math]O(n\log n)[/math] работает быстрее .

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

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

// j — счётчик пропущенных свободных позиций
// k — количество инверсий слева для элемента curr
// result — массив, в который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.
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


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

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

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

// build_segment_tree — строит дерево отрезков над массивом
// node — вершина дерева
// node.index — индекс соответствующего элемента в массиве для листа дерева
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


Этот алгоритм имеет сложность [math]O(n \log n)[/math]: делается [math]n[/math] итераций цикла, в которой происходит спуск по дереву высоты [math]O(\log n)[/math] и один запрос на дереве отрезков. Таким образом, время работы алгоритма на каждой итерации есть [math]O(\log n)[/math].

Пример

Рассмотрим пример построения таблицы инверсий и восстановления перестановки по таблице инверсий. Пусть дана перестановка [math](5, 7, 1, 3, 4, 6, 8, 2)[/math]. Следующая таблица показывает работу алгоритма за [math]O(n \log n)[/math], на каждой строке один уровень рекурсии (на первой строке — самый глубокий). В скобках стоят пары: элемент перестановки, количество инверсий. Полужирным отмечены элементы, у которых обновилось значение количества инверсий на данном шаге.

(5, 0) (7, 0) (1, 0) (3, 0) (4, 0) (6, 0) (8, 0) (2, 0)
(5, 0), (7, 0) (1, 0), (3, 0) (4, 0), (6, 0) (2, 1), (8, 0)
(1, 2), (3, 2), (5, 0), (7, 0) (2, 3), (4, 0), (6, 0), (8, 0)
(1, 2), (2, 6), (3, 2), (4, 2), (5, 0), (6, 1), (7, 0), (8, 0)

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

[math]0[/math] [math]0[/math] [math]\bf{1}[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math] пропускаем две свободных позиции и ставим [math]\bf{1}[/math]
[math]0[/math] [math]0[/math] [math]1[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]\bf{2}[/math] пропускаем шесть свободных позиций и ставим [math]\bf{2}[/math]
[math]0[/math] [math]0[/math] [math]1[/math] [math]\bf{3}[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]2[/math] пропускаем две свободных позиции и ставим [math]\bf{3}[/math]
[math]0[/math] [math]0[/math] [math]1[/math] [math]3[/math] [math]\bf{4}[/math] [math]0[/math] [math]0[/math] [math]2[/math] пропускаем две свободных позиции и ставим [math]\bf{4}[/math]
[math]\bf{5}[/math] [math]0[/math] [math]1[/math] [math]3[/math] [math]4[/math] [math]0[/math] [math]0[/math] [math]2[/math] не пропускаем свободных позиции и ставим [math]\bf{5}[/math]
[math]5[/math] [math]0[/math] [math]1[/math] [math]3[/math] [math]4[/math] [math]\bf{6}[/math] [math]0[/math] [math]2[/math] пропускаем одну свободную позицию и ставим [math]\bf{6}[/math]
[math]5[/math] [math]\bf{7}[/math] [math]1[/math] [math]3[/math] [math]4[/math] [math]6[/math] [math]0[/math] [math]2[/math] не пропускаем свободных позиций и ставим [math]\bf{7}[/math]
[math]5[/math] [math]7[/math] [math]1[/math] [math]3[/math] [math]4[/math] [math]6[/math] [math]\bf{8}[/math] [math]2[/math] не пропускаем свободных позиций и ставим [math]\bf{8}[/math]

См. также

Источники информации