Глава 17. Перестановки :: Идеи реализации

Идеи реализации
	Глава 17. Перестановки

Идеи реализации

Для перебора тасований мы воспользовались идеями из книги [6]. Начиная с тасования $〈11 \dots 1〉$ , будем увеличивать элементы этой последовательности на единицу, если это возможно, начиная с самого первого. Если же $k$ -й элемент невозможно увеличить, не нарушив неравенства $i_{k} ⩽ k$ , мы делаем $i_{k}$ равным единице, после чего переходим к следующему. Сразу скажем, что попытка увеличить первый элемент заведомо обречена на провал, поэтому можно начинать прямо со второго. Если уже не осталось элементов, которые можно увеличить, то есть получено тасование $〈123 \dots n〉$ , алгоритм останавливается.

Этот алгоритм очень похож на алгоритм перебора всех $n$ -значных натуральных чисел в некоторой системе счисления. Начиная с наименьшего числа, мы стараемся увеличить на единицу первую цифру, а когда это становится невозможным, берёмся за вторую, потом за третью, и так далее. Отличие заключается в том ограничении, которое должно выполняться при увеличении очередной цифры: результат должен быть меньше основания системы счисления. В нашем же случае для каждой «цифры» своё ограничение: нельзя превысить номер «разряда» (нумерация начинается с единицы).

Как отмечается в [6], алгоритм перебора чисел реализован в хорошо знакомом всем устройстве — механическом одометре, который служит для учёта пробега автомобиля, электрической энергии, воды или газа (рисунок 17.1. «Одометр (с сайта http://avto-all.com)»). Одометр состоит из набора колёс с нанесёнными на них цифрами. Колёса связаны таким образом, что полный оборот одного колеса вызывает поворот следующего на одну цифру. Так что когда возможности для увеличения цифр на данном колесе исчерпаны, цифра обнуляется, но зато делается попытка увеличить цифру на следующем колесе. Одометр — ещё одно полезное изобретение Герона Александрийского, сделанное на самой заре автомобилизма — в первом веке нашей эры.

Рисунок 17.1. Одометр (с сайта http://avto-all.com)

Если бы на первом колесе одометра была лишь одна цифра, на втором — две, на третьем — три, и так далее, мы получили бы прибор для построения тасований. Нам не удалось найти изображение такого усовершенствованного одометра, так что читателю придётся включить воображение.

Проиллюстрируем алгоритм на примере тасований трёхкарточной колоды. Вот полный перечень тасований, получаемых при его помощи: $〈1, 1, 1〉$ , $〈1, 2, 1〉$ , $〈1, 1, 2〉$ , $〈1, 2, 2〉$ , $〈1, 1, 3〉$ , $〈1, 2, 3〉$ .

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

Обратите внимание на то, что в предыдущих версиях программы мы никак не оговаривали порядок, в котором будут выводиться перестановки. Теперь же мы усложним задачу, потребовав, чтобы перестановки выводились в некотором естественном порядке.

Таким естественным способом упорядочить перестановки $σ \in S_{n}$ будет так называемый лексикографический порядок. При сравнении двух перестановок меньшей будет та, у которой на первом месте будет меньшее число. Если числа в первой позиции у обеих перестановок одинаковы, сравниваются вторые числа. Если же и они равны, сравниваются третьи, и так далее. Например, $(2, 1, 3) ≺ (2, 3, 1)$ , если зна́ком $≺$ мы обозначим отношение лексикографического «меньше». Приведём полное перечисление перестановок из $S_{3}$ в лексикографическом порядке: $(1, 2, 3) ≺ (1, 3, 2) ≺ (2, 1, 3) ≺ (2, 3, 1) ≺ (3, 1, 2) ≺ (3, 2, 1) .$ Выбор тождественной перестановки в качестве самой первой хорошо согласуется с лексикографическим порядком перебора перестановок, поскольку, очевидно, она является наименьшей в лексикографическом смысле. Между прочим, последней в списке всегда будет перестановка $(n n - 1 \dots 21)$ .

Совершенно невозможно не процитировать [8]:

В докладной записке, которую я написал (около 1917 года) для Баллистического управления, в конце была фраза «Таким образом, $σ$ следует сделать сколь возможно малым». В печатном тексте записки этой фразы не было. Но П. Дж. Григг сказал: «Что это такое?» Едва заметное пятнышко на пустом месте в конце оказалось миниатюрнейшим $σ$ , которое я когда-либо видел (наборщики, вероятно, обыскали весь Лондон).

Осталось выяснить, как преобразовать некоторую перестановку, чтобы получить из неё следующую в лексикографическом смысле. Введём обозначение $σ = (σ_{1} σ_{2} \dots σ_{n})$ для текущей перестановки. Заметим, что для самой последней перестановки в списке выполняются неравенства $σ_{1} > σ_{2} > \dots > σ_{n}$ . Если же найдётся такой номер $i \in \{12 \dots n\}$ , что $σ_{i} < σ_{i + 1}$ , $σ_{i + 1} > σ_{i + 2} > \dots > σ_{n - 1} > σ_{n}$ , это означает, что $σ_{i}$ может быть увеличена при переходе к следующей перестановке за счёт переупорядочения чисел $σ_{i} σ_{i + 1} \dots σ_{n}$ . Так как следующая перестановка является ближайшей в лексикографическом смысле, числа $σ_{1} σ_{2} \dots σ_{i - 1}$ должны остаться без изменений. Число $σ_{i}$ меняется местами с наименьшим из чисел $σ_{j}$ , стоящих правее его ( $j > i$ ), но при этом бо́льших, чем $σ_{i}$ . Затем числа $σ_{i + 1} \dots σ_{n}$ переупорядочиваются по возрастанию. Это несложно сделать, поскольку как до обмена $σ_{i} ⇄ σ_{j}$ , так и после него они упорядочены по убыванию — подумайте, почему. Значит, переупорядочения мы добьёмся, обменяв $σ_{i + 1} ⇄ σ_{n}$ , $σ_{i + 2} ⇄ σ_{n - 1}$ , …

В результате всех этих манипуляций перестановка $σ$ превратится в перестановку $σ^{'}$ такую, что $σ ≺ σ^{'}$ , причём наименьшую возможную.

Продемонстрируем превращение $σ$ в $σ^{'}$ на конкретном примере. Пусть $σ = (4, 2, 5, 3, 1)$ . Ищем $σ_{i}$ : $(4, 2, 5, 3, 1)$ . Теперь среди следующих за найденным числом $σ_{2} = 2$ найдём наименьшее из чисел, бо́льших чем $σ_{2}$ . Это $σ_{4} = 3$ . Меняем местами $σ_{2}$ и $σ_{4}$ : $(4, 3, 5, 2, 1)$ . Числа, следующие за $σ_{2}$ , упорядочены в порядке убывания. Переупорядочим их по возрастанию: $(4, 3, 1, 2, 5)$ . Перестановка $σ^{'}$ готова.


Глава 17. Перестановки		Разработка

Идеи реализации

Представление перестановок в программе

Рекурсивная реализация

Итеративные реализации

Тасование

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