Перестановки

Перестановками множества {a₁, a₂, …, a_n} называются расположения этого множества в различном порядке. Перестановка определяется последовательностью индексов располагаемых элементов, поэтому можно считать, что переставляются числа {1, 2, …, n}. Число n считается порядком перестановки. Всего имеется n! различных перестановок порядка n.

Есть разные способы представления перестановок. Простейший из них – указание последовательности чисел перестановки, например (2, 4, 1, 5, 3). Иногда удобно записывать перестановку в 2 строки, где первая задает места элементов, а вторая сами элементы, например

1, 2, 3, 4, 5

2, 4, 1, 5, 3

Если поменять строки местами и упорядочить столбцы по возрастанию чисел в первой строке, то получим перестановку, называемую обратной. Для перестановки A обратная перестановка обозначается A-1. В приведенном примере обратной будет перестановка

1, 2, 3, 4, 5

3, 1, 5, 2, 4

Произведение перестановок C = A´ B определяется следующим образом. Если в перестановке A на месте i находится элемент j, а в перестановке B на месте j элемент k, то в произведении C на месте i окажется k. Например,

1, 2, 3, 4, 5 ´ 1, 2, 3, 4, 5 = 1, 2, 3, 4, 5

2, 4, 5, 3, 1 5, 3, 1, 2, 4 3, 2, 4, 1, 5

Произведение перестановок некоммутативно, то есть A´ B ≠ B´ A.

Единичной называется перестановка (1, 2, …, n). Произведение любой перестановки на единичную как справа, так и слева не меняет ее, а произведение перестановки на обратную дает единичную перестановку. Таким образом, множество перестановок определенного порядка образуют группу.

В группе перестановок можно решить, например уравнение A´ X = B, где A и B – заданные перестановки. Умножая обе части уравнения слева на A-1, получим X = B´ A-1.

Распространенными задачами для перестановок являются генерация всех перестановок в определенном порядке и выбор случайной перестановки с равной вероятностью.

Начнем с задачи перечисления всех перестановок в лексикографическом порядке. Перестановка (α ₁, α ₂, …, α _n) лексикографически меньше перестановки (β 1, β 2, …, β n), если α _i = β _i при i = 1, …, k и α _i < β _i при i = k + 1. Лексикографический порядок называют иногда алфавитным. Действительно, именно такой принцип лежит в основе расположения слов по алфавиту. Например, при n= 3 в лексикографическом порядке следуют перестановки (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Если рассматривать эти перестановки как трехзначные числа, то лексикографический порядок совпадает с расположением чисел по возрастанию.

Приведем алгоритм перечисления перестановок порядка n в лексикографическом порядке.

Выбор начальной перестановки π = (π ₁, π ₂, …, π _n) = (1, 2, …, n).

Выдача перестановки π.

Просмотр перестановки π справа налево. Поиск самой правой позиции i такой, что π _i< π _i+1. Если это невозможно, то конец перебора (выдана последняя наибольшая перестановка).

Поиск π _j – наименьшего элемента справа от π _i такого, что π _j> π _i.

Транспозиция (обмен) элементов π _j и π _i. В результате π _i+1 > π _i+2 > …> π _n.

Начиная с позиции i+1 изменение элементов перестановки на π _n, π _n-1, …, π _i+1. Переход к 2.

Пусть, например, последняя выданная перестановка π = (2, 6, 5, 8, 7, 4, 3, 1). Здесь n =8, i = 3 и π _i =5, j = 5 и π _j =7. После транспозиции элементов π j и π i получается перестановка (2, 6, 7, 8, 5, 4, 3, 1), а после изменения мест конечных элементов приходим к следующей в лексикографическом порядке перестановке (2, 6, 7, 1, 3, 4, 5, 8).

Если перечислять перестановки порядка 5 с самого начала, то последовательно получим перестановки (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5), (1, 2, 4, 5, 3) и т. д.

Можно рекурсивно определить точное соответствие между целыми числами 0, 1, …, n! -1 и перестановками из множества {1, 2, …, n}, записанными в лексикографическом порядке [1].

Другой способ перечисления перестановок основан на векторах инверсий. Пусть X = (x₁, x₂, …, x_n) – некоторая перестановка элементов 1, 2, …, n. Пара (xi, xj) называется инверсией, если 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 таких, что пара (x_i, x_j) является инверсией. Иными словами d_j - это число элементов, больших xj и стоящих в перестановке X слева от xj. Очевидно, что 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). Таким образом, существует взаимно-однозначное соответствие (изоморфизм) между перестановками и векторами инверсий.

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

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

123 1243

12 132 1432

312 3142

1 4312

321 3421

21 231 2341

213 2413

Имея какой-либо способ нумерации перестановок порядка n, легко получить случайную перестановку, ставя ее в соответствие случайному целому числу из диапазона от 0 до (n-1)! Например, это можно сделать на основе лексикографического порядка перечисления перестановок. Существует вариант нумерации перестановок с помощью векторов инверсий [1]. Оба эти способа приводят к вычислительным трудностям при нахождении больших целых чисел.

Эффективный метод порождения случайных перестановок осуществляют последовательности из n-1 случайных транспозиций. Начиная с любой перестановки (π 1, π 2, …, π n), элемент π _n переставляется с одним из элементов π ₁, π ₂, …, π _n, выбираемым случайно. Затем π _n-1 меняется местами с одним из элементов π ₁, π ₂, …, π _n-1, выбираемым случайно и т. д.

Для того, чтобы показать, что все n! перестановок равновероятны, воспользуемся индукцией. Для n = 1 результат очевиден. Предположим, что алгоритм порождает случайные перестановки для n = k, то есть вероятность получения любой перестановки из k элементов составляет 1/k! Пусть при n=k+1 получена перестановка П=(π ₁, π ₂, …, π _k+1), в которой элемент k+1 оказался на месте j (1 ≤ j ≤ k+1). Поскольку на любом из этих k+1 мест элемент k+1 может быть в соответствии с алгоритмом с равной вероятностью, то вероятность перестановки

P(П) = P(π ₁, π ₂, …, π _j-1, π _j, π _j+1, …, π _k+1) = (1/k!) ´ P(π ₁, π ₂, …, π _j-1, π _j, …, π _k+1)=

=(1/k!) ´ 1/(k+1) = 1/(k+1)!

Следовательно, утверждение справедливо при n = k+1, то есть алгоритм порождает любую перестановку с равной вероятностью.