std::ranges::next_permutation, std::ranges::next_permutation_result

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 next_permutation_result<I>
    next_permutation( I first, S last, Comp comp = {}, Proj proj = {} );

template< ranges::bidirectional_range R, class Comp = ranges::less,
          class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr next_permutation_result<ranges::borrowed_iterator_t<R>>
    next_permutation( R&& r, Comp comp = {}, Proj proj = {} );

template< class I >
using next_permutation_result = ranges::in_found_result<I>;

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

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

Параметры

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

Исключения

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

Сложность

Не более \(\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 next_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::next_permutation_result<I>
        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        // проверка, что последовательность содержит как минимум два элемента
        if (first == last)
            return {std::move(first), false};
        I i_last{ranges::next(first, last)};
        I i{i_last};
        if (first == --i)
            return {std::move(i_last), false};
        // основной цикл "перестановок"
        for (;;)
        {
            I i1{i};
            if (std::invoke(comp, std::invoke(proj, *--i), std::invoke(proj, *i1)))
            {
                I j{i_last};
                while (!std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *--j)))
                {}
                std::iter_swap(i, j);
                std::reverse(i1, i_last);
                return {std::move(i_last), true};
            }
            // пространство перестановок исчерпано
            if (i == first)
            {
                std::reverse(first, i_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::next_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 next_permutation_fn next_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{"abc"};
    do
    {
        print(s);
    }
    while (std::ranges::next_permutation(s.begin(), s.end()).found);
    std::cout << "\n" "Generate all permutations (range case):\n";
    std::array a{'a', 'b', 'c'};
    do
    {
        print(a);
    }
    while (std::ranges::next_permutation(a).found);
    std::cout << "\n" "Generate all permutations using comparator:\n";
    using namespace std::literals;
    std::array z{"█"s, "▄"s, "▁"s};
    do
    {
        print(z);
    }
    while (std::ranges::next_permutation(z, std::greater()).found);
    std::cout << "\n" "Generate all permutations using projection:\n";
    std::array<S, 3> r{S{'A',3}, S{'B',2}, S{'C',1}};
    do
    {
        print(r, '\n');
    }
    while (std::ranges::next_permutation(r, {}, &S::c).found);
}

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

Смотрите также