Перестановкой называется упорядоченная выборка всех элементов конечного множества без повторений, где фиксировано взаимное расположение элементов. Различные перестановки совпадают по составу и отличаются позициями своих элементов. Например, для множества из 3-х латинских букв {X, Y, Z} можно получить следущие 6 различных перестановок:
( X Y Z); (Y Z X); (Z X Y); (Y X Z); (X Z Y); (Z Y X).
В общем случае для множества из n элементов можно построить n! Различных перестановок. Для любых целых положительных чисел n значение n! Можно вычислить по следующему рекуррентному соотношению:
n!= n(n-1)!; 0!=1.
Чтобы определить значение n! по этому рекуррентному соотношению нужно последовательно вычислить факториалы всех чисел от 1 до (n-1). Для непосредственной оценки значения n! без промежуточных умножений можно воспользоваться приближенной формулой Стирлинга:
n!~ 2pn(n/e)n
Относительная ошибка вычисления значения n! по формуле Стирлинга равна приблизительно (1/12n). Например, точное значение 8! Равно 40320, а вычисление по формуле Стирлинга дает приближенный результат 39902 с ошибкой около 1% (1/120):
40320= 8!~ 2??8(8/e)8~ 39902
Вычислительный эксперимент позволяет заметить быстрый рост значения n! при увеличении n. В частности, 10! Превышает 3,5 миллиона (3.628.800), а 1000! представляет собой целое число с более чем 2500 десятичными значениями. Еще один интересный факт заключается в том, что количество десятичных цифр в записи n! превышает n , начиная с n=25. В общем случаем можно показать, что факториальная функция растет быстрее экспоненты. Справедливость такого вывода следует из следующего анализа выражения для квадрата факториальной функции:
(n!)2=k(n-k+1) >= n=nn, откуда n!>=n(n/2)
Полученная оценка скорости роста факториальной функции имеет важное практическое значение, определяя вычислительную сложность решения различных комбинаторных задач, где требуется перебор перестановок различных элементов. Для решения таких задач были предложены комбинаторные алгоритмы систематического перечисления перестановок в различном порядке. Наиболее известными из них являются алгоритм перечисления перестановок в лексиграфическом порядке, алгоритм вращения перестановок и алгоритм транспозиции смежных элементов. Особенности реализации этих алгоритмов рассмотрены ниже.