std::next_permutation

Определено в заголовке `<algorithm>`
template< class BidirIt > bool next_permutation( BidirIt first, BidirIt last );	(1)	(constexpr начиная с C++20)
template< class BidirIt, class Compare > bool next_permutation( BidirIt first, BidirIt last, Compare comp );	(2)	(constexpr начиная с C++20)

Преобразует диапазон [first, last) в следующую перестановку. Возвращает true, если такая «следующая перестановка» существует; в противном случае преобразует диапазон в лексикографически первую перестановку (порядок по возрастанию) и возвращает false.

1) Множество всех перестановок упорядочено лексикографически относительно operator<(до C++20)std::less{}(начиная с C++20).

2) Множество всех перестановок упорядочено лексикографически относительно comp.

Если тип *first не является Swappable(до C++11)BidirIt не является ValueSwappable(начиная с C++11), поведение не определено.

Параметры

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

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

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

Сложность

Пусть \(\scriptsize N\)N — std::distance(first, last):

1,2) Не более \(\scriptsize \frac{N}{2}\)N/2 обменов.

Исключения

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

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

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;
}

Примечания

В среднем по всей последовательности перестановок типичные реализации выполняют около 3 сравнений и 1,5 обмена за вызов.

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

Пример

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

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>

int main()
{
    std::string s = "ABBA";
    std::sort(s.begin(), s.end());
    
    do
        std::cout << s << '\n';
    while (std::next_permutation(s.begin(), s.end()));

    assert(std::is_sorted(s.begin(), s.end()));
}

Вывод:

AABB
ABAB
ABBA
BAAB
BABA
BBAA

См. также

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

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