4.2. Перестановки различных элементов

Перестановки множества различных элементов относятся к часто порождаемым комбинаторным объектам. Без ограничения общности можно полагать, что элементами множества являются целые числа от 1 до , т. е. рассматриваются перестановки целых чисел

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

Алгоритм 4.2. Порождение перестановок методом поиска с возвращением

(см. скан)

Программа на языке Pascal реализации рассмотренного метода генерации перестановок приводится в алгоритме 4.3. Следует отметить, что в программе размерность перестановок читается из файла и порождаемые перестановки также сохраняются в файле. Попутно программа вычисляет время порождения всех перестановок с точностью до сотых долей секунды, которое сохраняется в конце файла сгенерированных перестановок.

Алгоритм 4.3. Программа на Pascalе порождения перестановок методом поиска с возвращением

(см. скан)

(см. скан)