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

Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithme (informellement appelés niebloids ), c'est-à-dire :

• Les listes d'arguments de template explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
• Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
• Lorsque l'une d'entre elles est trouvée par la recherche non qualifiée normale comme nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.

Paramètres

Valeur de retour

Exceptions

Toute exception levée par les opérations d'itérateur ou l'échange d'éléments.

Complexité

Au maximum \(\scriptsize N/2\) N / 2 échanges, où \(\scriptsize N\) N est ranges:: distance ( first, last ) dans le cas (1) ou ranges:: distance ( r ) dans le cas (2) . En moyenne sur l'ensemble de la séquence de permutations, les implémentations typiques utilisent environ 3 comparaisons et 1,5 échanges par appel.

Notes

Les implémentations (par exemple MSVC STL ) peuvent activer la vectorisation lorsque le type d'itérateur modélise contiguous_iterator et que l'échange de son type de valeur n'appelle ni fonction membre spéciale non triviale ni ADL -trouvée swap .

Implémentation possible

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
    {
        // vérifier que la séquence a au moins deux éléments
        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};
        // boucle principale de "permutation"
        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};
            }
            // l'espace de "permutation" est épuisé
            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 {};

Exemple

#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 << "Générer toutes les permutations (cas des itérateurs) :\n";
    std::string s{"abc"};
    do
    {
        print(s);
    }
    while (std::ranges::next_permutation(s.begin(), s.end()).found);
    std::cout << "\n" "Générer toutes les permutations (cas des ranges) :\n";
    std::array a{'a', 'b', 'c'};
    do
    {
        print(a);
    }
    while (std::ranges::next_permutation(a).found);
    std::cout << "\n" "Générer toutes les permutations en utilisant un comparateur :\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" "Générer toutes les permutations en utilisant une 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);
}

Générer toutes les permutations (cas des itérateurs) :
{ a b c } { a c b } { b a c } { b c a } { c a b } { c b a }
Générer toutes les permutations (cas des ranges) :
{ a b c } { a c b } { b a c } { b c a } { c a b } { c b a }
Générer toutes les permutations en utilisant un comparateur :
{ █ ▄ ▁ } { █ ▁ ▄ } { ▄ █ ▁ } { ▄ ▁ █ } { ▁ █ ▄ } { ▁ ▄ █ }
Générer toutes les permutations en utilisant une 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} }

Voir aussi