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

Пусть [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(N²)

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

[math]\mathtt{T}[1..n]\ =[/math] [math]0[/math]
for [math]i\ =[/math] [math]1..n[/math]
  for [math]j\ =[/math] [math]1..(i - 1)[/math]
    if [math]\mathtt{P}[j][/math] [math]\gt [/math] [math]\mathtt{P}[i][/math]
      [math]\mathtt{T}[\mathtt{P}[i]]\ =[/math] [math]\mathtt{T}[\mathtt{P}[i]]++[/math]

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

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

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

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

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

// [math]inverses\_merge[/math] — процедура, сливающая два списка пар
// [math]inverses\_get[/math] — процедура, рекурсивно получающая таблицу инверсий для перестановки
def  [math]\mathtt{inverses\_merge(ls1, ls2)}:[/math]
  [math]\mathtt{result}\ = [  ][/math]
  [math]it\textit{1}, it\textit{2}\ =[/math] null
  while [math](it\textit{1}[/math] [math]\lt [/math] [math]\mathtt{ls1.length})[/math] and [math](it\textit{2}[/math] [math]\lt [/math] [math]\mathtt{ls2.length}):[/math]
   if [math]\mathtt{ls1}[it\textit{1}]\mathtt{.item}[/math] [math]\lt [/math] [math]\mathtt{ls2}[it\textit{2}]\mathtt{.item}:[/math]
      [math]\mathtt{result.append}(\mathtt{ls1}[it\textit{1}])[/math]
      [math]it\textit{1}++[/math]
    else:
      [math]\mathtt{result.append}(item\ =[/math] [math]\mathtt{ls2}[it\textit{2}]\mathtt{.item}, inverses\ =[/math] [math]\mathtt{ls2}[it\textit{2}]\mathtt{.inverses}[/math] [math]+[/math] [math]\mathtt{ls1.length}[/math] [math]-[/math] [math]it\textit{1})[/math]
      [math]it\textit{2}++[/math]
  while [math](it\textit{1}[/math] [math]\lt [/math] [math]\mathtt{ls1.length}):[/math]
    [math]\mathtt{result.append}(\mathtt{ls1}[it\textit{1}])[/math]
    [math]it\textit{1}++[/math]
  while [math](it\textit{2}[/math] [math]\lt [/math] [math]\mathtt{ls2.length}):[/math]
    [math]\mathtt{result.append}(\mathtt{ls2}[it\textit{2}])[/math]
    [math]it\textit{2}++[/math]
  return [math]\mathtt{result}[/math]

def [math]\mathtt{inverses\_get(ls)}:[/math]
  if [math]\mathtt{ls.length}\ == 1:[/math]
    return [math][(item = \mathtt{ls[0]}, inverses = 0)][/math]
  else:
    return [math]\mathtt{inverses\_merge(inverses\_get(ls.first\_half), inverses\_get(ls.second\_half))}[/math]

Сложность представленного алгоритма есть [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] уже расставлены. Это рассуждение напрямую переписывается в код следующим образом:

// [math]j[/math] — счётчик пропущенных свободных позиций
// [math]k[/math] — количество инверсий слева для элемента curr
// [math]result[/math] — массив, в который записывается перестановка. Равенство элемента массива нулю обозначает, что эта позиция свободна.
def [math]\mathtt{recover\_straight(ls)}:[/math]
  [math]n\ = \mathtt{ls.length}[/math]
  [math]\mathtt{result}\ = \mathtt{array}(0, n)[/math]
  [math]curr\ = 1[/math]
  for [math]k \in \mathtt{ls}:[/math]
    [math]j\ = 0[/math]
    for [math](i\ = 0, i \lt  n, i++):[/math]
      if [math]\mathtt{result}[i]\ == 0:[/math]
        if [math]j\ == k:[/math]
          [math]\mathtt{result}[i]\ = curr[/math]
          break
        else:
          [math]j++[/math]
    [math]curr++[/math]
  return [math]\mathtt{result}[/math]

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

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

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

// [math]build\_segment\_tree[/math] — строит дерево отрезков над массивом
// [math]node[/math] — вершина дерева
// [math]node.index[/math] — индекс соответствующего элемента в массиве для листа дерева
def [math]\mathtt{recover(inv)}:[/math]
  [math]n\ = \mathtt{inv.length}[/math]
  [math]\mathtt{tree}\ = \mathtt{build\_segment\_tree}(\mathtt{array}(n, 1))[/math]
  [math]\mathtt{result}\ = \mathtt{array}(n)[/math]
  [math]curr\ = 1[/math]
  for [math]k \in \mathtt{inv}:[/math]
    [math]\mathtt{node}\ = \mathtt{tree.root}[/math]
    while [math](!\mathtt{node.is\_leaf}):[/math]
      if [math](k \lt \mathtt{node.left.value}):[/math]
        [math]\mathtt{node}\ = \mathtt{node.left}[/math]
      else:
        [math]k\ -= \mathtt{node.left.value}[/math]
        [math]\mathtt{node}\ = \mathtt{node.right}[/math]
    [math]\mathtt{result}[\mathtt{node.index}]\ = curr[/math]
    [math]\mathtt{node.add}(-1)[/math]
    [math]curr++[/math]
  return [math]\mathtt{result}[/math]

Этот алгоритм имеет сложность [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]

См. также

• Матричное представление перестановок

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

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