std::ranges::prev_permutation, std::ranges::prev_permutation_result

Определено в заголовке `<algorithm>`
Подпись вызова
template< std::bidirectional_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> constexpr prev_permutation_result<I> prev_permutation( I first, S last, Comp comp = {}, Proj proj = {} );	(1)	(с C++20)
template< ranges::bidirectional_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr prev_permutation_result<ranges::borrowed_iterator_t<R>> prev_permutation( R&& r, Comp comp = {}, Proj proj = {} );	(2)	(с C++20)
Вспомогательный тип
template< class I > using prev_permutation_result = ranges::in_found_result<I>;	(3)	(с C++20)

1) Преобразует диапазон [first, last) в предыдущую перестановку, где множество всех перестановок упорядочено лексикографически относительно объекта-функции двоичного сравнения comp и объекта-функции проекции proj.

Возвращает:

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

ranges::sort(first, last, comp, proj);
ranges::reverse(first, last);

2) То же, что (1), но использует r в качестве исходного диапазона, как если бы использовалось ranges::begin(r) в качестве first, и ranges::end(r) в качестве last.

Функциональные сущности, описанные на этой странице, являются niebloids, то есть:

Явные списки аргументов шаблона не могут быть указаны при вызове любого из них.
Ни один из них не виден для поиска зависимого от аргументов.
При обнаружении любого из них обычным безусловным поиском как имени слева от оператора вызова функции, поиск зависимый от аргументов ингибируется.

На практике они могут быть реализованы как объекты-функции или с помощью специальных расширений компилятора.

Параметры

first, last	-	диапазон элементов для "перестановки"
r	-	диапазон элементов для "перестановки"
comp	-	объект-функция сравнения, которая возвращает `true` , если первый аргумент меньше второго
proj	-	проекция для применения к элементам

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

1) ranges::prev_permutation_result<I>{last, true} , если новая перестановка лексикографически меньше старой. ranges::prev_permutation_result<I>{last, false} , если была достигнута первая перестановка и диапазон был сброшен до последней перестановки.

2) То же, что (1), за исключением того, что тип возвращаемого значения — ranges::prev_permutation_result<ranges::borrowed_iterator_t<R>>.

Исключение

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

Сложность

Максимум \(\scriptsize N/2\)N / 2 обменов, где \(\scriptsize N\)N — ranges::distance(first, last) в случае (1) или ranges::distance(r) в случае (2). В среднем по всей последовательности перестановок типичные реализации используют около 3 сравнений и 1,5 обменов на вызов.

Примечания

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

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

struct prev_permutation_fn
{
    template<std::bidirectional_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr ranges::prev_permutation_result<I>
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        // check that the sequence has at least two elements
        if (first == last)
            return {std::move(first), false};
        auto i{first};
        ++i;
        if (i == last)
            return {std::move(i), false};
        auto i_last{ranges::next(first, last)};
        i = i_last;
        --i;
        // main "permutating" loop
        for (;;)
        {
            auto i1{i};
            --i;
            if (std::invoke(comp, std::invoke(proj, *i1), std::invoke(proj, *i)))
            {
                auto j{i_last};
                while (!std::invoke(comp, std::invoke(proj, *--j), std::invoke(proj, *i)))
                    ;
                ranges::iter_swap(i, j);
                ranges::reverse(i1, last);
                return {std::move(i_last), true};
            }
            // permutation "space" is exhausted
            if (i == first)
            {
                ranges::reverse(first, last);
                return {std::move(i_last), false};
            }
        }
    }
 
    template<ranges::bidirectional_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::prev_permutation_result<ranges::borrowed_iterator_t<R>>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
};
 
inline constexpr prev_permutation_fn prev_permutation {};

Пример

#include <algorithm>
#include <array>
#include <compare>
#include <functional>
#include <iostream>
#include <string>
 
struct S
{
    char c{};
    int i{};
    auto operator<=>(const S&) const = default;
    friend std::ostream& operator<<(std::ostream& os, const S& s)
    {
        return os << "{'" << s.c << "', " << s.i << "}";
    }
};
 
auto print = [](auto const& v, char term = ' ')
{
    std::cout << "{ ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '}' << term;
};
 
int main()
{
    std::cout << "Generate all permutations (iterators case):\n";
    std::string s{"cba"};
    do print(s);
    while (std::ranges::prev_permutation(s.begin(), s.end()).found);
 
    std::cout << "\nGenerate all permutations (range case):\n";
    std::array a{'c', 'b', 'a'};
    do print(a);
    while (std::ranges::prev_permutation(a).found);
 
    std::cout << "\nGenerate all permutations using comparator:\n";
    using namespace std::literals;
    std::array z{"▁"s, "▄"s, "█"s};
    do print(z);
    while (std::ranges::prev_permutation(z, std::greater()).found);
 
    std::cout << "\nGenerate all permutations using projection:\n";
    std::array<S, 3> r{S{'C',1}, S{'B',2}, S{'A',3}};
    do print(r, '\n');
    while (std::ranges::prev_permutation(r, {}, &S::c).found);
}

Вывод:

Generate all permutations (iterators case):
{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }
Generate all permutations (range case):
{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }
Generate all permutations using comparator:
{ ▁ ▄ █ } { ▁ █ ▄ } { ▄ ▁ █ } { ▄ █ ▁ } { █ ▁ ▄ } { █ ▄ ▁ }
Generate all permutations using projection:
{ {'C', 1} {'B', 2} {'A', 3} }
{ {'C', 1} {'A', 3} {'B', 2} }
{ {'B', 2} {'C', 1} {'A', 3} }
{ {'B', 2} {'A', 3} {'C', 1} }
{ {'A', 3} {'C', 1} {'B', 2} }
{ {'A', 3} {'B', 2} {'C', 1} }

См. также

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

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