4.3. Эффективное порождение перестановок

Последовательность перестановок на множестве в которой соседние перестановки различаются так мало, как только возможно, — лучшее, на что можно надеяться с точки зрения

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

Данную последовательность перестановок можно порождать итеративно, получая каждую перестановку из предшествующей ей и небольшого количества добавочной информации. Это делается с помощью трех векторов: текущей перестановки обратной к ней перестановкир и записи направления в котором сдвигается каждый элемент если он сдвигается влево; если вправо; и 0, если не сдвигается).

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

Корректность алгоритма доказывается индукцией по Алгоритм порождения всех перестановок линеен, сложность его определяется как Алгоритм 4.4 — один из наиболее эффективных алгоритмов для порождения перестановок.

Рабочая программа на языке Pascal реализации эффективного метода генерации перестановок приводится в алгоритме 4.5.

В качестве примера в алгоритме 4.6 приводится программа реализации эффективного метода генерации перестановок, написанная на языке Си.

Алгоритм 4.4. Метод эффективного порождения перестановок

(см. скан)

Алгоритм 4.5. Программа на Pascale порождения перестановок эффективным методом

(см. скан)

(см. скан)

Алгоритм 4.6. Программа на Си порождения перестановок эффективным методом

(см. скан)

(см. скан)