std::prev_permutation

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

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

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

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

Параметры

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

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

Исключения

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

Сложность

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

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

template<class BidirIt>
bool prev_permutation(BidirIt first, BidirIt last)
{
    if (first == last)
        return false;
    BidirIt i = last;
    if (first == --i)
        return false;
    
    while (1)
    {
        BidirIt i1, i2;
        
        i1 = i;
        if (*i1 < *--i)
        {
            i2 = last;
            while (!(*--i2 < *i))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

Примечания

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

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

Пример

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

int main()
{
    std::string s = "cab";
    
    do
    {
        std::cout << s << ' ';
    }
    while (std::prev_permutation(s.begin(), s.end()));
    
    std::cout << s << '\n';
}

cab bca bac acb abc cba

См. также