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} и преобразует диапазон в лексикографически последнюю перестановку (в порядке убывания)

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

Описанные на этой странице функциональные сущности представляют собой объекты-функции алгоритмов (неформально известные как niebloids), то есть:

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

Параметры

first, last	-	пара итератор–сентинел, определяющая диапазон элементов для «перестановки»
r	-	`range` элементов для «перестановки»
comp	-	объект-функция сравнения FunctionObject, возвращающий `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)	генерирует следующую лексикографически большую перестановку диапазона элементов (объект-функция алгоритма)
ranges::is_permutation (C++20)	определяет, является ли одна последовательность перестановкой другой последовательности (объект-функция алгоритма)
next_permutation	генерирует следующую лексикографически большую перестановку диапазона элементов (шаблон функции и объект-функция алгоритма)
ranges::next_permutation (C++20)
prev_permutation	генерирует следующую лексикографически меньшую перестановку диапазона элементов (шаблон функции)
is_permutation (C++11)	определяет, является ли одна последовательность перестановкой другой последовательности (шаблон функции и объект-функция алгоритма)
ranges::is_permutation (C++20)

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