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

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

Определение:

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

Определение:

Таблицей инверсий перестановки [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].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источники

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