Перестановка – упорядоченный набор чисел 1, 2, 3, …, n, обычно трактуемый как биекция на множестве {1, 2, 3, … , n}, которая i-й элемент из набора ставит в позицию, равную элементу перестановки ai. Значение n называют порядком перестановки.
Количество всевозможных перестановок из n элементов:
Например, перестановка (5, 1, 6, 4, 2, 3) имеет 6-ю степень и последовательное ее применение приводит к следующей последовательности:
Любая последовательность применения перестановки приводит к циклу, который распадается на простые циклы:
Если L1, L2, …, Lk – длины простых циклов, то степень перестановки (длина всего цикла) равна:
L = НОК(L1, L2, …, Lk)
Значение L соответствует минимальному количеству применений перестановки к единичной перестановке так, что та переходит сама в себя, образуя цикл.
Перебор перестановок в C++
В библиотеке algorithm языка C++ есть функция next_permutation, которая позволяет по заданной перестановке получать следующую лексикографически минимальную. При этом функция возвращает true, если таковая перестановка существует. Очевидно, что для максимальной перестановки следующей не существует. В этом случае функция возвращает false и преобразует исходную максимальную перестановку в минимальную. В качестве входных данных может использоваться статический массив, вектор или строка:
В качестве входных данных для функции next_permutation может выступать не обязательно перестановка, то есть могут быть и повторяющиеся элементы. Также следует здесь упомянуть о существовании функции prev_permutation, которая позволяет получить предыдущую перестановку аналогичным образом.
С использованием функции next_permutation несложно организовать перебор всех возможных перестановок. Например, перебор всех возможных перестановок символов строки, заданной во входных данных, может быть следующим:
Next_permutation в Python
В стандартных библиотеках языка Python нет аналога функции next_permutation из C++. Однако, подобную функцию можно реализовать, например, следующим образом:
def next_permutation(a):
res = False
i = len(a)-2
while i>=0 and a[i]>=a[i+1]: i -= 1
if i>=0:
k = len(a)-1
while a[k]<=a[i]: k -= 1
a[i],a[k] = a[k],a[i]
res = True
a[i+1:] = reversed(a[i+1:])
return res
Тогда реализация аналогичного перебора всех возможных перестановок символов строки, заданной во входных данных, на языке Python при использовании вышеописанной функции будет следующей:
s = sorted(list(input()))
print(''.join(s))
while next_permutation(s):
print(''.join(s))
Заметим, что такая задача может быть решена с использованием функции permutations из библиотеки itertools следующим образом:
from itertools import permutations
for s in set(permutations(list(input()))):
print(''.join(s))
Однако, такое решение требует больше памяти и времени. Плюсом такого решения является только скорость реализации данного кода.
