std::next_permutation

Defined in header `<algorithm>`
	(1)
template< class BidirIt > bool next_permutation( BidirIt first, BidirIt last );		(до C++20)
template< class BidirIt > constexpr bool next_permutation( BidirIt first, BidirIt last );		(с C++20)
	(2)
template< class BidirIt, class Compare > bool next_permutation( BidirIt first, BidirIt last, Compare comp );		(до C++20)
template< class BidirIt, class Compare > constexpr bool next_permutation( BidirIt first, BidirIt last, Compare comp );		(с C++20)

Переставляет диапазон [first, last) в следующее перестановку, где множество всех перестановок упорядочено лексикографически относительно operator< или comp. Возвращает true , если такая "следующая перестановка" существует; в противном случае преобразует диапазон в первую лексикографически перестановку (как если бы с помощью std::sort(first, last, comp)) и возвращает false.

Параметры

first, last	-	диапазон элементов для перестановки
comp	-	объект-функция сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает `true` , если первый аргумент меньше второго. Подпись функции сравнения должна быть эквивалентна следующей: `bool cmp(const Type1& a, const Type2& b);` Хотя подпись не должна содержать `const&`, функция не должна изменять объекты, переданные ей, и должна уметь принимать все значения типа (возможно const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1&` недопустимо, а также `Type1` , если для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа BidirIt можно было дереференцировать и затем неявно преобразовать в оба из них.
Требования к типу
-`BidirIt` должен удовлетворять требованиям ValueSwappable и LegacyBidirectionalIterator.

Возвращаемое значение

true , если новая перестановка лексикографически больше, чем старая. false , если последняя перестановка была достигнута, и диапазон был сброшен до первой перестановки.

Исключения

Любые исключения, сгенерированные операциями итераторов или обменом элементов.

Сложность

Не более N/2 обменов, где N = std::distance(first, last). В среднем по всей последовательности перестановок типичные реализации используют около 3 сравнений и 1,5 обменов на вызов.

Примечания

Реализации (например, MSVC STL) могут включить векторизацию, когда тип итератора удовлетворяет LegacyContiguousIterator, а обмен его типом значения не вызывает ни нетривиальной специальной функции-члена, ни найденной swap.

Возможная реализация

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    auto r_first = std::make_reverse_iterator(last);
    auto r_last = std::make_reverse_iterator(first);
    auto left = std::is_sorted_until(r_first, r_last);
 
    if (left != r_last)
    {
        auto right = std::upper_bound(r_first, left, *left);
        std::iter_swap(left, right);
    }
 
    std::reverse(left.base(), last);
    return left != r_last;
}

Пример

Следующий код выводит все три перестановки строки "aba".

#include <algorithm>
#include <iostream>
#include <string>
 
int main()
{
    std::string s = "aba";
 
    do std::cout << s << '\n';
    while (std::next_permutation(s.begin(), s.end()));
 
    std::cout << s << '\n';
}

Вывод:

aba
baa
aab

См. также

is_permutation (C++11)	определяет, является ли последовательность перестановкой другой последовательности (шаблон функции)
prev_permutation	генерирует следующую меньшую лексикографическую перестановку диапазона элементов (шаблон функции)
ranges::next_permutation (C++20)	генерирует следующую большую лексикографическую перестановку диапазона элементов (niebloid)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/next_permutation