Транспозиция смежных элементов

Векторы инверсий

Пусть X = (x₁, x₂, …, x_n) – некоторая перестановка элементов 1, 2, …, n. Пара (x_i, x_j) называется инверсией, если i < j, а x_i < x_j. Например, в перестановке (5, 2, 1, 3, 4) имеются инверсии (5, 2), (5, 1), (5, 3), (5, 4), (2, 1). Вектором инверсий называют упорядоченное множество D = (d₁, d₂, …, d_n), где d_j – количество элементов x_i таких, что является инверсией. Иными словами d_j - это число элементов, больших x_j и стоящих в перестановке X слева от x_j. Очевидно, что d₁ = 0 и 0 ≤ d_j <j.

Вектор инверсий однозначно определяется по перестановке. Например, для перестановки X = (5, 2, 1, 3, 4) вектор инверсий D = (0, 1, 2, 1, 1).

С другой стороны, по корректному вектору инверсий однозначно восстанавливается перестановка. Пусть, например, D = (0, 1, 2, 1, 1). Будем рассматривать компоненты вектора инверсий справа налево. Поскольку d₅ = 1, то из чисел 1, 2, 3, 4, 5 лишь одно больше величины x₅. Значит, x₅ = 4. Так как d₅ = 0, то из оставшихся чисел 1, 2, 3, 5 на предпоследнем месте стоит наибольшее из них, то есть 5. Значение d₃ = 2 указывает, что среди чисел 1, 2, 3 в середине должно стоять третье по величине, то есть 1. В результате приходим к исходной перестановке X = (5, 2, 1, 3, 4). Таким образом, существует взаимнооднозначное соответствие (изоморфизм) между перестановками и векторами инверсий.

Условия d₁ = 0 и 0 ≤ d_j <j позволяют определить номер перестановки в смешанной системе счисления с факториалами

N(X) = d₁ + d₂*1! +d₃*2!+…+d_n*(n-1)!

Основаниями являются значения r₀ = 1, r₁ = 2,…, r_i = i +1, а числа находятся в диапазоне от 0 до n! - 1. Перестановкой с нулевым номером оказывается (1, 2, …, n), а наибольший номер n! – 1 имеет перестановка (n, n-1, …, 2, 1).

Вектора инверсий дают возможность применять другой по сравнению с лексикографическим способ перечисления перестановок. Изменяя номер перестановки от 0 до n! – 1, можно для каждого номера путем перевода в смешаную систему счисления с факториалами определить вектор инверсий и найти перестановку. Для выделения случайной перестановки можно получить ее номер в виде целого случайного числа в диапазоне от 0 до n! – 1 и затем через вектор инверсий восстановить перестановку.

Пусть, например, при n=5 получено случайное число 29 из интервала от 0 до 5!-1=119. Тогда N(X) = 0 + 1*1! + 2*2! + 0*3! + 1*4!, то есть D = (0, 1, 2, 0, 1), откуда X = (3, 2, 1, 5, 4).

Сумма координат вектора инверсий используется как мера “беспорядка” перестановки. Эта величина обращается в ноль для перестановки (1, 2, …, n), а наибольшего значения n*(n-1)/2 достигает на перестановке (n, n-1, …, 1).

Желательно, чтобы при перечислении соседние перестановки отличались как можно меньше. Минимальное различие может выражаться в транспозиции или обмене каких-либо двух соседних элементов перестановки.

Такую последовательность перестановок можно построить рекурсивно. При n=1 единственная перестановка, очевидно, удовлетворяет требованиям. Предположим, что мы имеем последовательность П₁, П₂, … перестановок на множестве {1, 2, …, n-1}, в которой последовательные перестановки различаются только транспозицией смежных элементов. Мы будем расширять каждую из этих (n-1)! перестановок, вставляя элемент n на каждое из n возможных мест следующим образом: n добавляется к П_i последовательно во все позиции справа налево, если i нечетно, и слева направо, если i четно. Порядок порождаемых таким образом перестановок будет следующим:

1234

123 1243

4132

12 132 1432

312 3142

1 4312

4321

321 3421

21 231 2341

213 2413

Дата добавления: 2014-01-11