Следует отметить, что итерации рассмотренных алгоритмов обязательно должны начинаться с лексиграфически наименьшей или наибольшей перестановки, если требуется перечислить все перестановки. Это ограничение становится обременительным, когда важно иметь возможность начать перечисление с произвольной перестановки. Такую возможность предоставляет алгоритм вращения перестановок.
Алгоритм вращения реализует итерационный процесс, на каждом шаге которого получение очередной перестановки обеспечивает циклический сдвиг элементов предыдущей перестановки на 1 позицию вправо. При каждом таком сдвиге последний элемент перемещается на первую позицию без изменения взаимного расположения остальных элементов перестановки. Например, циклический сдвиг букв слова WORD порождает новую перестановку букв этого слова:
(WORD)>> (DWOR).
Указанная организация циклического сдвига называется вращением. Вращение всех элементов перестановки можно и нужно продолжать, пока оно позволяет порождать новые перестановки, не встречавшиеся прежде. Например, последовательные полные вращения порождают следующую последовательность перестановок букв слова LEX(закон), которая завершается повтором исходной перестановки:
(LEX)0>>(XLE)1>>(EXL)2>>(LEX)
- ^ ^
В общем случае повторение одной из прежних перестановок происходит, когда позиция последнего сдвигаемого элемента после вращения (Х) совпадает с его исходным положением в начальной перестановке. В этой ситуации нужно исследовать возможность получить новую перестановку применяя вращение в сокращенном диапазоне, последовательно для первых j= n-1, n-2, ... 2 элементов при фиксированном положении (n-j) хвостовых элементов. В частности, сокращение диапазона вращения повторной перестановки LEX до 2-х начальных позиций сразу порождает новую перестановку ELX:
...(LEX)0>>(ELX)3...
- ~~
В общем случае после получения новой перестановки указанным способом следует продолжить итерации вращения в полном диапазоне, порождая очередную серию оригинальных перестановок. Например, вращение всех элементов перестановки (ELX) порождает еще 2 новые перестановки до очередного повтора перестановки (ELX), с которой начиналась вторая серия полных вращений и которая совпадает с исходной по позиции элемента Х:
...(ELX)3>>(XEL)4>>(LXE)5>>()>>(X)0
Сокращение диапазона вращения повторной перестановки (ELX) до 2-х позиций теперь не порождает новой перестановки (из-за совпадения по позиции элемента Е), т.к. получается исходная перестановка (LEX). Диапазон вращения нужно уменьшить уже до одной позиции. В данном и общем случае, когда диапазон вращения сокращается до одной позиции, выполнение итерации алгоритма должно быть завершено, потому что перечислены все перестановки.
Следует отметить, что соседние перестановки, полученные алгоритмом вращения существенно различаются расположением своих элементов. В частности, любая итерация полного вращения изменяет позиции всех элементов, чтобы получить новую перестановку. Это чрезвычайно неэффективно даже если не учитывать затраты на обработку повторов вращением в сокращенном диапазоне.