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

Выберем наиболее простой способ хранить найденные перестановки в программе: массив. Если перестановки предстоит помещать в список, для такого списка подойдёт массив ссылок на анонимные массивы, в каждом из которых будет размещаться перестановка. Вот как будет выглядеть структура, хранящая все шесть перестановок из множества S 3 : ([3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]).

Для реализации рекурсивного алгоритма нужно исходную задачу — поиск перестановок из S n  — свести к решению таких же задач (поиск перестановок из S k для некоторых k). Если решение основной задачи оформить в виде процедуры permutations, принимающей параметр $n, то такая процедура помогала бы сама себе, рекурсивно вызывая себя для решения вспомогательных задач.

Такое представление есть, и оно удивительно просто. Достаточно знать множество S n 1 , чтобы найти S n . Из каждой n 1 -перестановки σ S n 1 наделаем n штук новых n-перестановок. Для этого в каждую перестановку σ нужно вставить число n всевозможными способами. Сколько всего таких способов? Конечно, n. К примеру, для 3-перестановки 2 1 3 после указанных манипуляций получатся 4-перестановки 4 2 1 3 , 2 4 1 3 , 2 1 4 3 , 2 1 3 4  — всего 4 штуки.

Кстати, мы получили одно из доказательств того факта, что количество n-перестановок равно n ! . Это доказательство по индукции. Вообще, индукция в математике очень близка по смыслу к рекурсии в информатике.

Параметр n при вызове процедуры permutations — это количество элементов в некотором множестве, поэтому допустимые значения этого параметра — целые неотрицательные числа. Поэтому особого внимания требует граничный случай, когда n = 0 . Что должна возвратить процедура permutations в этом случае? Список перестановок пустого множества. Сколькими способами можно упорядочить все (ноль) элементов пустого множества? Только одним — вот таким: . Именно так, хоть это и выглядит странно. Таким образом, при n = 0 процедура permutations должна вернуть одноэлементный список перестановок; единственная перестановка в этом списке — это пустой список чисел 1 2 0 , то есть .

Основная часть процедуры permutations, таким образом, будет содержать двойной цикл. Во внешнем будут перебираться n 1 -перестановки. Во внутреннем будут перебираться все способы, которыми можно вставить число n в каждую из них.

Наблюдения за работой рекурсивной программы выявляют существенный недостаток рекурсивного подхода. Программа некоторое время ничего не выводит на экран, накапливая перестановки в списке. Это означает, что к моменту вывода первой строчки найдены и помещены в массив все n! перестановок. С учётом того, что n! очень быстро растёт с ростом n, мы рискуем очень быстро исчерпать всю доступную память компьютера.

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

Осталось лишь выяснить, какую перестановку из S n мы выберем в качестве первой, и каким способом мы станем переходить от текущей перестановки к следующей. Иными словами, нужно описать порядок перебора элементов σ S n .

Совершенно естественно выбрать в качестве начальной перестановки тождественную 1 2 n , которая всегда содержится в S n , какое бы n мы ни взяли.

Взглянем на n-элементное множество X как на карточную колоду. Каждая из перестановок этого множества получается в результате некоторого тасования колоды. Если бы удалось перебрать все возможные варианты тасования, можно было бы получить все перестановки. Такой перебор возможен.

Тасование представим как последовательность из n транспозиций карт. Сначала последняя карта меняется местами с любой картой из колоды (очень важно не исключить по ошибке случай, когда карта меняется местами сама с собой). На следующем шаге предпоследняя карта меняется с любой, за исключением последней. Потом предпредпоследняя — с любой, кроме двух последних, и так далее. Так мы дойдём до первой карты колоды, которой не останется ничего другого, как обменяться местами самой с собой. Такой подход позволяет представить тасование как n-элементную последовательность номеров карт i 1 i 2 i n 1 i n , где i k k для всех k 1 n . Для того, чтобы выполнить закодированное в виде такой последовательности тасование, нужно менять местами карты с номерами k и i k , последовательно уменьшая k от n до 1. Например, для последовательности 1 1 3 2 3 5 получается перестановка 4 1 6 2 3 5 как результат цепочки транспозиций: 1 2 3 4 5 6 , 1 2 3 4 6 5 , 1 2 6 4 3 5 , 1 4 6 2 3 5 , 1 4 6 2 3 5 , 4 1 6 2 3 5 .

Пока что остаётся открытым вопрос о том, как организовать перебор таких последовательностей. Но прежде следует выяснить, имеется ли взаимно-однозначное соответствие между последовательностями и перестановками множества. Иными словами, любая ли перестановка может быть получена таким способом, и не дадут ли разные тасования одну и ту же перестановку?

На второй из этих вопросов ответ отрицательный: нет, не дадут. Пусть имеется два различных тасования I = i 1 i n и J = j 1 j n . Тогда найдётся хотя бы одно такое k, что i k j k . Выберем наибольшее из таких k. Возьмём колоду и начнём тасовать. Тогда при тасованиях I и J, очевидно, на k-м месте окажутся разные карты, так что разным тасованиям соответствуют разные перестановки.

Осталось доказать, что каждой перестановке отвечает некоторое тасование. Проще всего убедиться в этом подсчётом тасований. Для элементов последовательности, задающей тасование, имеем i 1 = 1 , i 2 1 2 , i 3 1 2 3 , и так далее. Таким образом, количество тасований равно 1 2 n = n ! , то есть совпадает с количеством перестановок. С учётом того, что разным тасованиям отвечают разные перестановки, получаем взаимно-однозначное соответствие.

Для перебора тасований мы воспользовались идеями из книги [6]. Начиная с тасования 1 1 1 , будем увеличивать элементы этой последовательности на единицу, если это возможно, начиная с самого первого. Если же k-й элемент невозможно увеличить, не нарушив неравенства i k k , мы делаем i k равным единице, после чего переходим к следующему. Сразу скажем, что попытка увеличить первый элемент заведомо обречена на провал, поэтому можно начинать прямо со второго. Если уже не осталось элементов, которые можно увеличить, то есть получено тасование 1 2 3 n , алгоритм останавливается.

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

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


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

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

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

Таким естественным способом упорядочить перестановки σ 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 2 1 .

Информатика-54© А. Н. Швец