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
    {
        // проверка, что последовательность содержит как минимум два элемента
        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;
        // основной цикл "перестановок"
        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};
            }
            // пространство "перестановок" исчерпано
            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 << "Генерация всех перестановок (случай с итераторами):\n";
    std::string s{"cba"};
    do print(s);
    while (std::ranges::prev_permutation(s.begin(), s.end()).found);
    std::cout << "\nГенерация всех перестановок (случай с диапазоном):\n";
    std::array a{'c', 'b', 'a'};
    do print(a);
    while (std::ranges::prev_permutation(a).found);
    std::cout << "\nГенерация всех перестановок с использованием компаратора:\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 << "\nГенерация всех перестановок с использованием проекции:\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);
}

Вывод:

Генерация всех перестановок (случай с итераторами):
{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }
Генерация всех перестановок (случай с диапазоном):
{ c b a } { c a b } { b c a } { b a c } { a c b } { a b c }
Генерация всех перестановок с использованием компаратора:
{ ▁ ▄ █ } { ▁ █ ▄ } { ▄ ▁ █ } { ▄ █ ▁ } { █ ▁ ▄ } { █ ▄ ▁ }
Генерация всех перестановок с использованием проекции:
{ {'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)

Поддержка компиляторов
Автономные и размещённые
Язык
Стандартная библиотека
Заголовки стандартной библиотеки
Именованные требования
Макросы проверки возможностей (C++20)
Библиотека поддержки языка
Библиотека концепций (C++20)
Библиотека диагностики
Библиотека управления памятью
Библиотека метапрограммирования (C++11)
Библиотека общих утилит
Библиотека контейнеров
Библиотека итераторов
Библиотека диапазонов (C++20)
Библиотека алгоритмов
Библиотека строк
Библиотека обработки текста
Библиотека численных операций
Библиотека даты и времени
Библиотека ввода/вывода
Библиотека файловой системы (C++17)
Библиотека поддержки параллелизма (C++11)
Библиотека управления выполнением (C++26)
Технические спецификации
Индекс символов
Внешние библиотеки

ru.cppreference.net

Namespaces

Variants