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

Чтобы лучше понять смысл следующей или предыдущей лексикографической перестановки, рассмотрим такую последовательность из трех символов: >abc. У этой последовательности есть шесть возможных вариантов перестановки: >abc, >acb, >bac, >bca, >cab и >cba. Эти варианты перестановки перечислены в лексикографическом порядке на основании оператора "меньше". Таким образом, вариант перестановки >abc будет первым, поскольку его первый элемент меньше или равен первому элементу любого другого варианта перестановки, а ее второй элемент меньше, чем у любого другого варианта с тем же первым элементом. Точно так же >acb — следующий вариант перестановки, поскольку он начинается с символа >а, который меньше первого элемента любого из остальных вариантов перестановки. Варианты перестановки, начинающиеся с >b, располагаются перед таковыми, начинающимися с >c.

Для каждого описанного выше варианта перестановки можно выяснить, какой из них должен располагаться прежде, а какие после него. Например, варианте перестановки >bca можно сказать, что предыдущим для нее будет вариант >bac, а следующим — >cab. Для варианта >abc нет предыдущего, а для варианта >cba — последующего варианта перестановки.

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

Для осуществления перестановки нужна возможность перебора последовательности вперед и назад, поэтому им требуются двунаправленные итераторы.

>is_permutation(beg1, end1, beg2)

>is_permutation(beg1, end1, beg2, binaryPred)

Алгоритмы возвращают значение >true, если во второй последовательности есть вариант перестановки с тем же набором элементов, что и в первой последовательности, для которой элементы в варианте перестановки и в исходной последовательности равны. Первая версия сравнивает элементы, используя оператор >==; вторая использует заданный предикат >binaryPred.

>next_permutation(beg, end)

>next_permutation(beg, end, comp)

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

>prev_permutation(beg, end)

>prev_permutation(beg, end, comp)

Подобен алгоритму >next_permutation(), но преобразует последовательность в предыдущую версию перестановки. Если текущая версия является самой младшей, переупорядочивает последовательность в самую старшую и возвращает значение