В некоторых случаях важно иметь количественную оценку степени отличия произвольной перестановки от лексиграфически наименьшей по числу нарушений возрастающего порядка значений элементов. Любая пара элементов, где имеет место указанное нарушение их взаимного расположения в перестановке называется инверсией. Более строго, любая упорядоченная пара элементов (pi,pj) перестановки p=(p1, ...pi, ... pj, ...pn) образует инверсию, если pi>pj и i<j. Например, цифровая перестановка (3, 1, 4, 2) имеет 3 инверсии: (3, 1), (3, 2) и (4, 2). Таким образом, в этой перестановке есть одна инверсия для элемента 1, две инверсии элемента 2, а по элементам 3 и 4 нет инверсий.
Для компактной записи распределения числа инверсий по элементам перестановки применяется вектор инверсий V=(V1,...Vj, ... Vn) и таблица инверсий W(W1, ...Wj, ... Wn). Обе формы записи идентифицируют числа инверсий для всех элементов перестановки и отличаются только различным порядком их перечисления. В частности, в векторе инверсий числа инверсий упорядочены по позициям элементов, а в таблице инверсий- по значениям элементов перестановки. Формально, компоненты вектора и таблицы инверсий Vj и Wj, соответственно, определяются следующим образом:
Vj=|{Pi>Pj, i<j}| и Wj=|{Pi>j, i<j}|
Состав вектора и таблицы инверсий для произвольной цифровой перестановки Р= (5, 9, 1, 8, 2, 6, 4, 7, 3) показан в следующем примере, где для наглядности индексированы позиции всех элементов:
В частности, в этом примере V8=2, потому что слева от элемента P8=7 в перестановке есть 2 элемента P2=9 и P4=8 с большим значением, чем 7. С другой стороны W8=1, потому что слева от элемента со значением 8 это P4 в перестановке есть только один элемент P2=9, значение которого больше, чем 8. Аналогичным образом можно обосновать выбор величин остальных компонентов вектора и таблицы инверсий в данном примере. Следует также отметить, что для любой перестановки V1=Wn=0, а значения остальных компонентов вектора и таблицы инверсий связаны следующими соотношениями:
Vj=Wi | i=Pj или Wj=Vi | Pi=j
Возвращаясь к интегральным оценкам, следует отметить, что суммарное значение компонентов вектора или таблицы инверсий определяет общее число инверсий перестановки. В рассмотренном выше примере оно, в частности, равно 20. Максимальная сумма числа инверсий имеет место в лексиграфически наибольшей перестановке и в общем случае она равна n(n-1)/2. Нулевое число инверсий имеет лексиграфически наименьшая перестановка.
Кроме информации о распределении беспорядка в перестановке, вероятно, наиболее практически важный факт состоит в том, что вектор и таблица инверсий однозначно определяют перестановки, которым они соответствуют. Это значит, что любая перестановка может быть всегда однозначно восстановлена по соответствующему вектору или таблице инверсий. Для практического выполнения этих преобразований предусмотрены следующие 2 алгоритма восстановления.
В частности, при использовании вектора инверсий элементы перестановки нужно последовательно вычислять справа налево в порядке уменьшения индекса, а их значения должны выбираться из списка упорядоченным по убыванию целых чисел от n до1. При этом значение очередного элемента Pj принимается равным (Vj+1) по величине числу списка, а выбранное число должно быть исключено из списка. Это процесс повторяется для вычисления значений всех элементов перестановки. Рассмотренный алгоритм иллюстрирует следующий пример восстановления перестановки из 5-ти элементов по вектору инверсий V=(0, 1, 2, 0,1):
P5<-4 P4<-5 P3<-1 P2<-2 P1<-3
<5 4 3 2 1>, <5 3 2 1>, <3 2 1>, <3 2>, <3>
- ^ ^ ^ ^ ^
V: V5=1 V4=0 V3=2 V2=1 V1=0
Таким образом в результате восстановления, в этом примере из заданного вектора инверсий образуется следующая перестановка Р=(3 2 1 5 4). Нетрудно проверить, что она соответствует исходному вектору инверсий.
Более изящный алгоритм разработан для восстановления перестановки по таблице инверсий. В этом алгоритме нужно последовательно просматривать компоненты таблицы инверсий Wj справа налево (j=n, n-1, ... 1), формируя из их индексов список, который показывает относительное расположение элементов искомой перестановки со значениями: n, (n-1), ... 1, соответственно. Сначала в пустой список включается элемент со значением n. На каждом последующем шаге очередной элемент со значением j располагается так, чтобы в списке перед ним оказалось Wj элементов, значение которых больше, чем j. После размещения последнего элемента со значением 1 в списке получается искомая перестановка, которая соответствует заданной таблице инверсий. Рассмотренный алгоритм иллюстрирующий пример последовательного формирования перестановки из 5-ти элементов по таблице инверсий W= (2, 1, 0, 1, 0):
L: (5), (5 4), (3 5 4), (3 2 5 4), (3 2 1 5 4) ->P
- ^ ^ ^ ^ ^
- W5=0 W4=1 W3=0 W2=1 W1=2 <-W
В этом примере символ '^' показывает элемент, размещаемый в списке L на каждой итерации, в результате выполнения которых образуется искомая перестановка Р=(3 2 1 5 4). Несложно проверить ее соответствие заданной таблице инверсий. Можно также заметить, что полученная перестановка совпадает с перестановкой, построенной по вектору инверсий в предыдущем примере. В связи с этим можно лишний раз проконтролировать равенство между компонентами вектора и таблицы инверсий, которые соответствуют по позициям и значениям элементов перестановки:
W5=V4(P4=5); W4=V5(P5=4); W3=V1 (P1=3); W2=V2(P2=2); W1=V3(P3=1)
В рассмотренных алгоритмах восстановления перестановки неявно учтены численные ограничения по значению компонентов вектора и таблицы инверсий. Они также следуют из их формального определения и имеют следующий вид:
0<=Vj<j и 0<=Wj<=(n-j); j=1,2,....n
Эти ограничения почти такие же, что предъявляются к цифрам в системах счисления с факториалами. Поэтому векторы и таблицы инверсий можно рассматривать как целочисленные значения, представленные в системах счисления с возрастающими и убывающими факториалами, где учтено равенство нулю значений V1 и Wn:
Nv=V2 1! + V3 2! + V4 3!+ ... +Vn(n-1)!; (V1=0);
Nw=W1(n-1)! + W2(n-2)!+ ... + Wn-1 1!; (Wn=0);
При этом всегда возможно выполнить однозначное обратное преобразование, которое восстанавливает компоненты вектора или таблицы инверсий по заданному целому числу. Например, несложно проверить следующие взаимо однозначные соответствия:
V=(0, 0, 2, 1) <-> N=10 <-> W(1, 2, 0, 0).
С другой стороны, соответствие между перестановками и векторами или таблицами инверсий предоставляет возможность использовать их численные эквиваленты для нумерации перестановок. Например, перестановке Р=(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
Следующий пример иллюстрирует результат вычисления алгоритмом инверсий последовательности цифровых перестановок из 3-х элементов при использовании вектора и таблице инверсий:
В этом примере и в общем случае алгоритм инверсий порождает последовательности перестановок с нулевым числом инверсий и заканчиваются лексиграфически наибольшей перестановкой, где число инверсий максимально. При этом у каждой промежуточной перестановки число инверсий не меньше, чем у предыдущей. Таким образом получаются последовательности перестановок, частично упорядоченные по суммам инверсий своих элементов.