std::prev_permutation

Определён в заголовочном файле `<algorithm>`
template< class BidirIt > bool prev_permutation( BidirIt first, BidirIt last );	(1)	(constexpr с C++20)
template< class BidirIt, class Compare > bool prev_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` должен удовлетворять требованиям ValueSwappable и LegacyBidirectionalIterator.

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

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

Исключения

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

Сложность

Обозначим через \(\scriptsize N\)N std::distance(first, last):

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

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

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.

Пример

Следующий код выводит все шесть перестановок строки "cab" в обратном порядке.

#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

См. также

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

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