Функция next_permutation

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

Синтаксис

next_permutation(first, last)
next_permutation(first, last, comp)

Пример

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

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

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

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

1 3 2

Пример

Давайте переберём все возможные перестановки вектора 1, 2, 3 в цикле:

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

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

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

Пример

Давайте проверим, что произойдёт, если вызвать функцию для последней перестановки вектора 3, 2, 1:

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

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

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

false
1 2 3

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

функция prev_permutation,
которая получает предыдущую перестановку
функция sort,
которая сортирует элементы диапазона
функция reverse,
которая меняет порядок элементов на обратный
функция rotate,
которая выполняет циклический сдвиг элементов