Функция prev_permutation

Функция prev_permutation из заголовочного файла algorithm преобразует последовательность элементов в предыдущую перестановку в лексикографическом порядке. Если предыдущая перестановка существует, функция возвращает true, в противном случае - false и преобразует последовательность в последнюю (максимальную) перестановку. В первый и второй параметры мы передаем итераторы начала и конца последовательности. Третий параметр необязательный - это функция сравнения, которая определяет порядок сортировки.

Последовательность должна быть отсортирована по возрастанию (или в соответствии с заданным компаратором), чтобы функция корректно выполнила свою работу.

Синтаксис

prev_permutation(first, last)
prev_permutation(first, last, comp)

Пример

Давайте получим предыдущую перестановку для вектора {3, 2, 1}:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> res = {3, 2, 1};
	bool success = prev_permutation(res.begin(), res.end());
	
	cout << boolalpha << success << endl;
	for (int n : res)
	{
		cout << n << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

true
3 1 2

Пример

Давайте получим предыдущую перестановку, когда она не существует - для вектора, который уже является минимальной перестановкой:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> res = {1, 2, 3};
	bool success = prev_permutation(res.begin(), res.end());
	
	cout << boolalpha << success << endl;
	for (int n : res)
	{
		cout << n << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

false
3 2 1

Пример

Давайте переберём все перестановки вектора в обратном порядке, используя цикл:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> res = {3, 2, 1};
	
	do
	{
		for (int n : res)
		{
			cout << n << " ";
		}
		cout << endl;
	} while (prev_permutation(res.begin(), res.end()));
	
	return 0;
}

Результат выполнения кода:

Смотрите также

функция next_permutation,
которая возвращает следующую перестановку
функция sort,
которая сортирует последовательность
функция reverse,
которая переворачивает последовательность
функция is_sorted,
которая проверяет, отсортирована ли последовательность