std::ranges:: prev_permutation, std::ranges:: prev_permutation_result

ranges::sort(first, last, comp, proj);
ranges::reverse(first, last);

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

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{"cba"};
    do print(s);
    while (std::ranges::prev_permutation(s.begin(), s.end()).found);
    std::cout << "\nGénérer toutes les permutations (cas des plages) :\n";
    std::array a{'c', 'b', 'a'};
    do print(a);
    while (std::ranges::prev_permutation(a).found);
    std::cout << "\nGé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::prev_permutation(z, std::greater()).found);
    std::cout << "\nGénérer toutes les permutations en utilisant une 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} }

Voir aussi