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

Перестановками множества {a₁, a₂, …, a_n} называются расположения этого множества в различном порядке [1]. Перестановка определяется последовательностью индексов располагаемых элементов, поэтому можно считать, что переставляются числа {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) лексикографически меньше перестановки (β₁, β₂, …, β_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 в лексикографическом порядке.

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

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

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

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

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

6. Начиная с позиции 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. Пара (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 таких, что пара (x_i, x_j) является инверсией. Иными словами 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). Таким образом, существует взаимно-однозначное соответствие (изоморфизм) между перестановками и векторами инверсий.

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

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

1234

123 1243

1423

4123

4132

12 132 1432

1342

1324

3124

312 3142

3412

1 4312

4321

321 3421

3241

3214

2314

21 231 2341

2431

4231

4213

213 2413

2143

2134

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

Эффективный метод порождения случайных перестановок осуществляют последовательности из n-1 случайных транспозиций. Начиная с любой перестановки (π₁, π₂, …, π_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, k+1, π_j+1,…, π_k+1) = (1/k!) P(π₁, π₂, …, π_j-1, π_j+1,…, π_k+1)=

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

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

Задачи для самостоятельного решения

8.1. Слова (3)

Дана строка, состоящая из M символов. Вывести все перестановки символов данной строки.

Ввод из файла INPUT.TXT. В первой строке файла находится исходная строка.

Вывод в файл OUTPUT.TXT. Вывести в каждой строке файла по одной перестановке.

Ограничения: 2 ≤ M ≤ 8, символы - буквы латинского алфавита и цифры, время 1 с.
Перестановки можно выводить в любом порядке. Повторений и строк, не являющихся перестановками исходной, быть не должно.

Примеры

Ввод 1 Ввод 2

AB 122

Вывод 1 Вывод 2

AB 122

BA 212

221

2. Простые примеры на перестановки (6)

Составить программы для решения следующих задач:

1. решить уравнение на перестановках вида AX = B, где A и B - заданные перестановки, а X - неизвестная перестановка;

2. по заданной перестановке из N элементов выдать K следующих перестановок в лексикографическом порядке;

3. по заданной перестановке построить вектор инверсий, а по вектору инверсий восстановить перестановку;

4. перечислить перестановки из N элементов путем транспозиции смежных элементов с рекурсией и без нее.

Входные данные задавать с клавиатуры, вывод результатов - на экран.

8.3. Матрица (8)

В матрице A размера NN числа от 1 до N². Каждое число записано ровно один раз. Даны две матрицы размера NN: Top и Left. Значение Top_{i j} определяет количество чисел, больших A_{i j} и расположенных выше по столбцу, Left_{i j} - количество чисел, больших A_{i j} и расположенных левее по строке. Найти возможные значения матрицы A. Если решений несколько, вывести любое.

Ввод из файла INPUT.TXT. В первой строке N (1 ≤ N ≤100), затем N строк матрицы Top (числа через пробел), затем N строк матрицы Left. Числа в обеих матрицах от 0 до N.

Вывод в файл OUTPUT.TXT матрицы A – N строк, числа в строке через пробел. Если решений нет, вывести 0.

Пример

Ввод

3

0 0 0

0 0 0

0 0 2

0 0 0

0 1 0

0 1 2

Вывод

1 2 6

5 3 7

9 8 4

Подсказка. Основной принцип – проставлять очередное число в цикле от 1 до N² в такую клетку (i, j), где i –номер строки, а j – номер столбца, значение которой должно быть наименьшим среди незаполненных клеток строки i и столбца j. Это свойство нужно уметь проверять по матрицам Top и Left. Тогда заполненная матрица не будет противоречить заданным условиям. Различных решений может быть много.

8.4. Перестановки (9)

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p₁, p₂, …, p_n} будет лексикографически меньше перестановки {q₁, q₂, …, q_n}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого p_j = q_j при j < i и p_i < q_i.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

Требуется написать программу, позволяющую найти m-ую k-перестановку в этом порядке.

Ввод из файла INPUT.TXT. В первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 10⁹). Вторая строка содержит n различных натуральных чисел, не превосходящих 10⁹. Все числа в строках разделены пробелом.

Вывод. В выходной файл OUTPUT.TXT необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

Примеры

Ввод 1 Ввод 2 Ввод 3

4 1 2 4 4 2 4 5 2

6 8 3 9 6 8 3 9 6 8 3 9

Вывод 1 Вывод 2 Вывод 3

3 9 6 8 9 3 6 8 -1

Подсказка. Для сокращения вычислений стоит заранее по алгоритму Евклида [4] найти наибольший общий делитель по всем парам чисел. Полное решение данной задачи основано на использовании динамического программирования и эффективном кодировании подмножества исходного множества. В качестве подзадач здесь следует рассматривать задачи, аналогичные исходной, но для некоторого подмножества исходного множества чисел. Выберем в качестве состояния пару из подмножества P исходного множества S и номера выделенного элемента j в нем. Для каждого состояния будем хранить количество существующих k–перестановок из элементов данного подмножества P, но только таких перестановок, в которых последний элемент имеет номер j (в исходной нумерации). Начальное состояние в этом случае будет P=Ø. При программной реализации подмножество P удобно хранить с помощью битовых масок.

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

Описанные алгоритм имеет время работы O(m²2^m). Несмотря на то, что данное решение работает за экспоненциальное время, оно значительно быстрее простого перебора.