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


где Si - элемент исходного множества, расположенный в i-й позиции перестановки.

Конечное множество из n элементов можно упорядочить n! различными способами, получив n! перестановок, которые отличаются только порядком элементов. Например, для множества из 3-х элементов:


можно построить 3! (6) перестановок:


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