Изменения

Сопоставим каждому элементу перестановки <tex>p[i]</tex> направление <tex>d[i]</tex>. Будем указывать направление при помощи стрелок '''←''' ("влево") или '''→'''("вправо"). Назовём элемент подвижным, если по направлению стелки стоит элемент меньше его. Например , для <tex> p = \{1, 3, 2, 4, 5\},\;d = \{</tex>←, →, ←, →, ←<tex>\}</tex>, подвижными являются элементы 3 и 5. На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего. Изначально <tex> p = \{1, ... ,n\},\;d = \{</tex>←, ... ,←<tex>\}</tex>.

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

*<tex>(a,</tex> ←<tex>)</tex> <tex> - </tex> элемент с заданным направлением(компонента).*<tex>P[i]</tex> <tex> - </tex> перестановка с номером <tex>i</tex>.*<tex>P[i]\backslash\{a\}\;</tex> <tex> - </tex> перестановка с номером <tex>i</tex> без элемента <tex>a</tex>.