Иногда важно иметь количественную оценку степени отличия произвольной перестановки от лексиграфически наименьшей по числу нарушений возрастающего порядка значений ее элементов. Любая пара элементов, где имеет место такое нарушение их взаимного положения в перестановке, называется инверсией. Формально любая пара элементов (pi, pj) из перестановки (p1,…,pi,…,pj,…,pn) образует инверсию, если pi>pj и i<j. Например, цифровая перестановка (3,1,4,2) имеет 3 инверсии: (3,1), (3,2) и (4,2). Таким образом, в этой перестановке есть одна инверсия для элемента 1, две инверсии для элемента 2, а по элементам 3 и 4 нет инверсий.
Для компактной записи инверсий по элементам перестановки применяются вектор инверсий (V1,…Vj,…Vn) и таблица инверсий (W1,…Wj,…Wn). Эти обе формы записи идентифицируют числа инверсий для всех элементов перестановки (p1,…pj,…pn) и отличаются только порядком их перечисления. В частности, в векторе инверсий числа инверсий упорядочены по позициям, а в таблице инверсий по значениям элементов перестановки. Формально, компоненты вектора и таблицы инверсий, определяются следующим образом:
Vj = | { pi > pj : i < j } | и Wj = | { pi > j : i < j } |.
Состав вектора и таблицы инверсий для цифровой перестановки P=(5,9,1,8,2,6,4,7,3) показан в следующем примере, где для наглядности индексированы позиции всех элементов:
Таблица 1    
j123456789
pj591826473
Vj002132426
Wj236402219

В частности, в этом примере V8=2, потому что слева от элемента P8=7 в перестановке есть 2 элемента P2=9 и P4=8 с большим значением, чем 7. С другой стороны, W8=1,потому что слева от элемента со значением 8 (это P4) в перестановке имеется только 1 элемент (P2=9), значение которого больше, чем 8. Аналогичным образом можно обосновать выбор величин остальных компонентов вектора и таблицы инверсий в данном примере. Следует также отметить, что для любой перестановки значения компонентов вектора и таблицы инверсий связаны следующими соотношениями:
V1 = Wn = 0; Vj = Wi | i = Pj; Wj = Vi | Pi = j.
Возвращаясь к интегральным оценкам, следует отметить, что сумма значений всех компонентов вектора или таблицы инверсий определяет общее число инверсий I перестановки. В частности, для рассмотренного примера оно равно 20:
I(5, 9, 1, 8, 2, 6, 4, 7, 3) = 20.
В общем случае число инверсий произвольной перестановки из n элементов всегда лежит в пределах от 0, у лексиграфически наименьшей перестановки, до максимального значения, равного n(n−1)/2, которое имеет лексигафически наибольшая перестановка:
I(1, 2, …, n−1, n) = 0 ≤ I(p1, …, pi, …, pn) ≤ I(n, n−1, …, 2, 1) = n(n-1)2
Кроме информации о распределении беспорядка в перестановке, важное практическое значение имеет тот факт, что вектор и таблица инверсий однозначно определяют перестановки, которым они соответствуют. Это означает, что любая перестановка может быть всегда однозначно восстановлена по соответствующему вектору или по таблице инверсий. Для выполнения этих преобразований предусмотрены следующие два алгоритма восстановления.
В частности, при восстановлении из вектора инверсий V, элементы искомой перестановки P нужно последовательно вычислять справа налево в порядке уменьшения индекса, а их значения должны выбираться из списка L упорядоченных по убыванию целых чисел от n до 1. При этом значение очередного элемента перестановки pi принимается равным (Vi+1)-му по величине числу списка L. После этого выбранное число должно быть исключено из списка. Выполнение алгоритма иллюстрирует следующий пример восстановления перестановки P=(3,2,1,5,4) по вектору инверсий V=(0,1,2,0,1):
p:4->p5 5->p4 1->p3 2->p2 3->p1L:{5 ^4^ 3 2 1}<5 ^3^ 2 1>,<3 2 ^1^>,<3 ^2^>,<^3^>V: 1=V5 0=V4 2=V3 1=V2 0=V1
В этом примере символ '^' указывает элемент, который исключается из списка L на каждой итерации, для передачи его значения очередному элементу перестановки. В частности, сначала из списка пяти чисел <54321> нужно исключить второй по величине элемент (4), так как последний элемент вектора инверсий равен 1, и значение 4 назначается последнему элементу перестановки. Аналогичные действия повторяются на всех последующих шагах.
Более изящный алгоритм разработан для восстановления перестановки P по таблице инверсий W. В этом алгоритме нужно последовательно просматривать компоненты таблицы инверсий Wi справа налево от i=n до i=1, чтобы получить из их индексов список L, который показывает относительное расположение элементов pi искомой перестановки со значениями от n до 1, соответственно. Сначала в пустой список включается элемент со значением n. На каждом следующем шаге очередной элемент со значением i располагается так, чтобы в списке перед ним оказалось Wi элементов, значения которых больше, чем i. После размещения последнего элемента со значением 1 в списке получается искомая перестановка, которая соответствует заданной таблице инверсий. Этот алгоритм иллюстрирует следующий пример, где из таблицы инверсий W=(2,1,0,1,0) последовательно формируется перестановка P=(3,2,1,5,4):
L: ( 5^ ),( 5 4^ ), ( 3^ 5 4),( 3 2^ 5 4), ( 3 2 1^ 5 4) ->p W->W5=0W4=1W3=0W2=1W1=1
В этом примере символ '^' указывает элемент, размещаемый в списке L на каждой итерации, в результате выполнения которых образуется искомая перестановка P. Несложно проверить ее соответствие заданной таблице инверсий. Можно также заметить, что полученная перестановка совпадает с перестановкой, построенной по вектору инверсий в предыдущем примере. В связи с этим полезно лишний раз проверить соблюдение равенства между компонентами вектора и таблицы инверсий, которые соответствуют по позициям и значениям элементов перестановки:
W5=V (p=5); W4=V (p=4); W3=V (p=3); W2=V (p=2); W1=V (p=1).
В рассмотренных алгоритмах восстановления перестановок неявно учтены ограничения по значению компонентов вектора и таблицы инверсий. Они также следуют из их формального определения и имеют следующий вид:
0 < Vj < j; 0 < Wj < (n − j); j = 1, 2, …, n.
Эти ограничения почти такие же, что применяются к цифрам факториальных систем счисления. Поэтому векторы и таблицы инверсий можно рассматривать как целочисленные значения, представленные в системах счисления с возрастающими и убывающими факториалами. Их величины вычисляются, соответственно, по следующим формулам, где учтено равенство нулю значений V1 и Wn:
N = V2·1! + V3·2! + V4.3! + … + Vn·(n−1)! и N = W1·(n−1)! + W2·(n−2)! + … + Wn−1·1! .
При этом всегда возможно выполнить обратное преобразование, которое позволяет однозначно восстановить компоненты вектора или таблицы инверсий по любому заданному целому числу. Например, несложно проверить следующие взаимно однозначные соответствия:
V = (0, 0, 2, 1) <−> N = 10 <−> W = (1, 2, 0, 0).
С другой стороны соответствие между перестановками и векторами или таблицами инверсий предоставляет возможность использовать их численные эквиваленты для последовательной нумерации перестановок. Например, перестановке P=(4,2,1,3) соответствует номер NV=11 по вектору инверсий V=(0,1,2,1) или номер NW=15 по таблице инверсий W=(2,1,1,0). Все эти факториальные нумерации и однозначные соответствия позволяют предложить следующий алгоритм порождения перестановок в порядке, индуцированном векторами или таблицами инверсий. Нужно только перечислить целые числа от 0 до (n−1)! включительно, представляя каждое из них в форме вектора или таблицы инверсий, по которым затем восстанавливаются соответствующие перестановки. Указанные преобразования алгоритма инверсий отображает следующая формальная запись его итераций:
Pv <− V <− N −> W−> Pw
Следующий пример иллюстрирует результат вычисления алгоритмом инверсий всех цифровых перестановок из трех элементов 1, 2 и 3 при использовании вектора и таблицы инверсий:
Таблица 2    
Пv(123)(213)(132)(123)(312)(321)
V(000)(010)(001)(011)(002)(012)
N012345
W(000)(010)(100)(110)(200)(210)
Пw(123)(132)(213)(312)(231)(321)

В этом примере, как и в общем случае, алгоритм инверсий порождает последовательность перестановок, которая начинается с лексиграфически наименьшей перестановки с нулевым числом инверсий и заканчивается лексиграфически наибольшей перестановкой, где число инверсий максимально. При этом у каждой промежуточной перестановки число инверсий не меньше, чем у предыдущей перестановки. Таким образом, получаются последовательности перестановок, частично упорядоченные по суммам инверсий своих элементов.