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

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmusfunktionsobjekte (informell als Niebloids bekannt), das heißt:

• Explizite Vorlagenargumentlisten können beim Aufruf einer von ihnen nicht angegeben werden.
• Keine von ihnen sind für die argumentabhängige Namenssuche sichtbar.
• Wenn eine von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird die argumentabhängige Namenssuche unterbunden.

Parameter

Rückgabewert

Exceptions

Alle Ausnahmen, die von Iteratoroperationen oder dem Elementaustausch ausgelöst werden.

Komplexität

Höchstens \(\scriptsize N/2\) N / 2 Vertauschungen, wobei \(\scriptsize N\) N gleich ranges:: distance ( first, last ) in Fall (1) oder ranges:: distance ( r ) in Fall (2) ist. Im Durchschnitt über die gesamte Permutationssequenz verwenden typische Implementierungen etwa 3 Vergleiche und 1,5 Vertauschungen pro Aufruf.

Hinweise

Implementierungen (z.B. MSVC STL ) können Vektorisierung ermöglichen, wenn der Iteratortyp contiguous_iterator modelliert und das Vertauschen seines Werttyps weder nicht-triviale spezielle Elementfunktionen noch ADL -gefundene swap -Funktionen aufruft.

Mögliche Implementierung

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
    {
        // Überprüfen, ob die Sequenz mindestens zwei Elemente enthält
        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};
        // Haupt-"Permutations"-Schleife
        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};
            }
            // Permutations-"Raum" ist erschöpft
            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 {};

Beispiel

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

Siehe auch