Одним из наиболее естественных способов порождения перестановок является циклический сдвиг их элементов влево или вправо. В частности, при циклическом сдвиге вправо каждый элемент переходит в следующую позицию, вытесняя последний элемент в начало перестановки. При этом можно сдвигать все элементы или любое число головных элементов без изменения позиций хвостовых элементов перестановки. В следующем примере показаны 3 различных варианта организации циклического сдвига вправо элементов исходной перестановки (DEMO), после которых получаются другие перестановки, а сдвигаемые элементы подчеркнуты:

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

S₄ = ; S₃ = ; S₂ = ;

Во всех случаях столбцы любой подстановки задают последовательность переходов элементов исходной перестановки в элементы результирующей перестановки. В частности, 3 подстановки, рассмотренные выше, реализуют следующие циклические последовательности переходов своих элементов, которые составляют 1, 2 и 3 цикла переходов, соответственно:

Выполнение последовательных преобразований, заданных двумя или больше подстановками, обеспечивает произведение подстановок. Его результатом является транзитивное замыкание переходов элементов в перемножаемых подстановках. Например, произведение подстановок S₄ и S₃ образует следующую подстановку S:

S = S₄∙S₃ = = .

Такой результат обеспечивает следующая схема четырех транзитивных замыканий переходов элементов, реализуемых этими подстановками, где все переходы маркируются обозначениями подстановок, в которых они происходят:

Важным частным случаем произведения подстановок является вычисление степени, когда одна подстановка умножается сама на себя требуемое число раз. В следующем примере указанным образом вычисляется третья степень подстановки S:

S³ = S²∙S = = =

Наименьшая степень, при которой получается тождественная подстановка 1, устанавливает порядок подстановки. Например, рассмотренные выше подстановки S₄ S₃ и S₂ имеют порядки 4, 3 и 2, соответственно. В частности, следующее вычисление степени 3 подстановки S₃ дает тождественную подстановку 1:

S33 = = = 1.

Можно заметить, что для циклических подстановок, задающих преобразование циклического сдвига перестановок, порядок равен числу сдвигаемых элементов, а степень определяет число позиций, на которое перемещается каждый сдвигаемый элемент. Например, циклический сдвиг трех начальных элементов перестановки (DEMO) на 2 позиции вправо задает вторую степень подстановки порядка 3:

S23 = = .

Все эти циклические подстановки и перестановки интересны потому, что любая из них может быть записана единственным образом в виде произведения других подстановок различных порядков и степеней. Это позволяет получить любую перестановку из n элементов с номером N по соответствующей подстановке S(N), которая образуется произведением всех подстановок с последовательными порядками j от n до 1 и степенями d_j:

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

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

Конкретные значения степеней подстановок d_j по следующему представлению номера искомой подстановки N в системе счисления с убывающими факториалами:

Пусть, например, нужно определить перестановку с номером N=7, которую можно получить циклическим сдвигом элементов исходной перестановки (DEMO) из n=4 элементов. Тогда соответствующая ей подстановка должна представляться произведением подстановок порядков 4, 3, 2 и 1. Их степени определяет следующая запись номера 7 искомой подстановки четырех разрядным числом в системе счисления с убывающими факториалами, где значения разрядов перечислены в обратном порядке:

Таким образом, искомая подстановка с номером N=7 должна представляться произведением куба подстановки порядка 4 и первой степени подстановки порядка 3, а степени всех остальных подстановок меньших порядков равны 0:

S(7) = S34S13S02S01 = = .

Следовательно, седьмая перестановка, которая может быть получена из исходной перестановки (DEMO) циклическим сдвигом есть (DEOM):

Рассмотренное свойство произведения подстановок особенно удобно, когда необходимо найти перестановку по ее порядковому номеру в списке циклических сдвигов без перечисления всех предыдущих перестановок. Кроме того, это свойство формально обеспечивает возможность перечисления всех перестановок при любом числе элементов n систематическим перебором всех n! вариантов выбора порядков и степеней в произведениях соответствующих подстановок:

Практически нужно просто перечислять последовательные n-разрядные числа, записанные в системе счисления с убывающими факториалами, вычисляя для каждого из них произведение подстановок соответствующих степеней и порядков. Для иллюстрации в следующей таблице приведены факториальные номера и соответствующие им произведения подстановок из n=4 элементов:

Алгоритмически такой систематический перебор реализует следующий итерационный процесс циклических сдвигов. Его иногда называют алгоритмом вращения перестановок, а сам термин "вращение" считается синонимом понятия "циклический сдвиг". Выполнение этого алгоритма начинается с выбора произвольной исходной перестановки (p₁…p_j…p_n). Следующие (n−1) перестановок получается циклическим сдвигом (вращением) всех n элементов предыдущей перестановки на одну позицию вправо. Итерации вращения всех элементов позволяют получить новые перестановки, еще не встречавшиеся прежде. В общем случае каждая такая серия полных вращений завершается повтором исходной перестановки, с которой она началась:

Формальным признаком повтора является совпадение позиции последнего элемента сдвига с его позицией в исходной перестановке. В этой ситуации необходимо исследовать возможность получить новую перестановку, последовательно сокращая порядок сдвига на 1 от (n−1) до двух первых элементов при фиксированном положении хвостовых элементов текущей повторной перестановки. В данном случае, после первой серии полных вращений, получение очередной перестановки обеспечивает циклический сдвиг первых (n−1) элементов:

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

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

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