std::prev_permutation

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

Преобразует диапазон [first, last) в предыдущую перестановку из набора всех перестановок, упорядоченных лексикографически по отношению к operator< или comp. Возвращает true , если такая перестановка существует, в противном случае преобразует диапазон в последнюю перестановку (как если бы с помощью std::sort(first, last); std::reverse(first, last);) и возвращает 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 , если была достигнута первая перестановка, и диапазон был сброшен до последней перестановки.

Исключение

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

Сложность

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

Примечания

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

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

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

Пример

Следующий код выводит все шесть перестановок строки "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)	определяет, является ли последовательность перестановкой другой последовательности (шаблон функции)
next_permutation	генерирует следующую большую лексикографическую перестановку диапазона элементов (шаблон функции)
ranges::prev_permutation (C++20)	генерирует предыдущую меньшую лексикографическую перестановку диапазона элементов (niebloid)

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