Понятие перестановки

Перестановка – упорядоченный набор чисел 1, 2, 3, …, n, обычно трактуемый как биекция на множестве {1, 2, 3, … , n}, которая i-й элемент из набора ставит в позицию, равную элементу перестановки a_i. Значение n называют порядком перестановки.

Количество всевозможных перестановок из n элементов:

Например, перестановка (5, 1, 6, 4, 2, 3) имеет 6-ю степень и последовательное ее применение приводит к следующей последовательности:

(1,2,3,4,5,6) → (2,5,6,4,1,3) → (5,1,3,4,2,6) →
(1,2,6,4,5,3) → (2,5,3,4,1,6) → (5,1,6,4,2,3) → (1,2,3,4,5,6)

Любая последовательность применения перестановки приводит к циклу, который распадается на простые циклы:

Если L₁, L₂, …, L_k – длины простых циклов, то степень перестановки (длина всего цикла) равна:

L = НОК(L₁, L₂, …, L_k)

Значение L соответствует минимальному количеству применений перестановки к единичной перестановке так, что та переходит сама в себя, образуя цикл.

Перебор перестановок в C++

В библиотеке algorithm языка C++ есть функция next_permutation, которая позволяет по заданной перестановке получать следующую лексикографически минимальную. При этом функция возвращает true, если таковая перестановка существует. Очевидно, что для максимальной перестановки следующей не существует. В этом случае функция возвращает false и преобразует исходную максимальную перестановку в минимальную. В качестве входных данных может использоваться статический массив, вектор или строка:

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

С использованием функции next_permutation несложно организовать перебор всех возможных перестановок. Например, перебор всех возможных перестановок символов строки, заданной во входных данных, может быть следующим:

Next_permutation в Python

В стандартных библиотеках языка Python нет аналога функции next_permutation из C++. Однако, подобную функцию можно реализовать, например, следующим образом:

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

Заметим, что такая задача может быть решена с использованием функции permutations из библиотеки itertools следующим образом:

Однако, такое решение требует больше памяти и времени. Плюсом такого решения является только скорость реализации данного кода.