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

Пусть [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]i[/math] (где [math]i[/math] от [math]n[/math] до 1) на позицию [math]k+1[/math], где [math]k[/math] - число в таблице инверсий на [math]i[/math]-том месте. Данный алгоритм довольно прост в реализации, но без использования дополнительных структур данных, имеет сложность [math]O(n^2)[/math], т. к. для вставки элемента в определённую позицию, требуется порядка [math]n[/math] перестановок элементов.

Приведём алгоритм восстановления с использованием сортировки слиянием, имеющий сложность [math]O(n\log_2n)[/math].

Пусть [math]\alpha[/math] и [math]\beta[/math] - цепочки упорядоченных пар целых неотрицательных чисел [math][m_1, n_1]\dots[m_k, n_k][/math]. Рассмотрим двоичную операцию [math]\circ[/math], рекурсивно определенную на парах таких цепочек следующим образом:

$([m, n]\alpha)\circ([m', n']\beta)=\left\{\begin{aligned}[]
[m,n](\alpha \circ ([m'-m, n']\beta)), m \le m',\\
[m', n'](([m-m'-1, n]\alpha) \circ \beta), m>m'.\\
\end{aligned}
\right.$

Сопоставим каждому элементу таблицы инверсий его номер. Получится множество упорядоченных пар чисел [math][m_1, n_1]\dots[m_k, n_k][/math], где [math]m_i[/math] — сам элемент, а [math]n_i[/math] — его номер. Разобьём данные элементы на пары и произведём с ними операцию [math]\circ[/math]. Получим некоторое количество цепочек упорядоченных пар. Также разбиваем их на пары и производим операцию [math]\circ[/math]. Так действуем, пока не останется одна цепочка. Выписывая вторые элементы данных упорядоченных пар в том порядке, в каком они представлены в цепочке, получим первоначальную перестановку.

Цепочка наподобие [math][4, 4][1,3][/math] представляет "_ _ _ _ 4 _ 3 _ [math]\infty[/math]", где "_" означает пропуск. Операция [math]\alpha \circ \beta[/math] вставляет пропуски и заполнения из [math]\beta[/math] на место пропусков в [math]\alpha[/math].

Пример

• [math][4, 1, 6, 3, 2, 2, 1, 1, 1, 0][/math] - таблица инверсий.
• [math][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][/math]
• [math][1,2][2,1]\circ[3,4][2,3], [2,5][0,6]\circ[1,7][0,8], [0,10][0,9][/math]
• [math][1,2][2,1][0,4][2,3]\circ[1,7][0,5][0,6][0,8], [0,10][0,9][/math]
• [math][1,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3]\circ[0,10][0,9][/math]
• [math][0,10][0,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3][0,9][/math]

Получаем перестановку [math][10, 2, 7, 5, 1, 4, 6, 8, 3, 9][/math]

Источники

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