std::next_permutation

template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );

template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );

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

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

Параметры

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

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

Сложность

Пусть \(\scriptsize N\)N равно std::distance(first, last):

Исключения

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

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

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

См. также