Namespaces
Variants

std:: prev_permutation

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
prev_permutation

C library
Numeric operations
Operations on uninitialized memory
Défini dans l'en-tête <algorithm>
template < class BidirIt >
bool prev_permutation ( BidirIt first, BidirIt last ) ;
(1) (constexpr depuis C++20)
template < class BidirIt, class Compare >
bool prev_permutation ( BidirIt first, BidirIt last, Compare comp ) ;
(2) (constexpr depuis C++20)

Transforme la plage [ first , last ) en la permutation précédente. Retourne true si une telle permutation existe, sinon transforme la plage en la dernière permutation (comme avec std::sort suivi de std::reverse ) et retourne false .

1) L'ensemble de toutes les permutations est ordonné lexicographiquement par rapport à operator < (jusqu'en C++20) std:: less { } (depuis C++20) .
2) L'ensemble de toutes les permutations est ordonné lexicographiquement par rapport à comp .

Si le type de * first n'est pas Swappable (jusqu'à C++11) BidirIt n'est pas ValueSwappable (depuis C++11) , le comportement est indéfini.

Table des matières

Paramètres

first, last - la paire d'itérateurs définissant l' intervalle des éléments à permuter
comp - objet fonction de comparaison (c'est-à-dire un objet qui satisfait aux exigences de Compare ) qui renvoie true si le premier argument est inférieur au second.

La signature de la fonction de comparaison doit être équivalente à ce qui suit :

bool cmp ( const Type1 & a, const Type2 & b ) ;

Bien que la signature n'ait pas besoin d'avoir const & , la fonction ne doit pas modifier les objets qui lui sont passés et doit pouvoir accepter toutes les valeurs de type (éventuellement const) Type1 et Type2 indépendamment de la catégorie de valeur (ainsi, Type1 & n'est pas autorisé , pas plus que Type1 sauf si pour Type1 un déplacement équivaut à une copie (depuis C++11) ).
Les types Type1 et Type2 doivent être tels qu'un objet de type BidirIt puisse être déréférencé puis implicitement converti vers les deux.

Exigences de type
-
BidirIt doit satisfaire aux exigences de ValueSwappable et LegacyBidirectionalIterator .

Valeur de retour

true si la nouvelle permutation précède l'ancienne dans l'ordre lexicographique. false si la première permutation a été atteinte et que la plage a été réinitialisée à la dernière permutation.

Exceptions

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

Complexité

Étant donné N comme std:: distance ( first, last ) :

1,2) Au maximum
N
2
échanges.

Implémentation possible 

template<class BidirIt>
bool prev_permutation(BidirIt first, BidirIt last)
{
    if (first == last)
        return false;
    BidirIt i = last;
    if (first == --i)
        return false;
    while (1)
    {
        BidirIt i1, i2;
        i1 = i;
        if (*i1 < *--i)
        {
            i2 = last;
            while (!(*--i2 < *i))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

Notes

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.

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

Exemple

Le code suivant affiche les six permutations de la chaîne "cab" dans l'ordre inverse.

Exécuter ce code 
#include <algorithm>
#include <iostream>
#include <string>
int main()
{
    std::string s = "cab";
    do
    {
        std::cout << s << ' ';
    }
    while (std::prev_permutation(s.begin(), s.end()));
    std::cout << s << '\n';
}

Sortie : 

cab bca bac acb abc cba

Voir aussi

(C++11)
détermine si une séquence est une permutation d'une autre séquence
(modèle de fonction)
génère la prochaine permutation lexicographique supérieure d'une plage d'éléments
(modèle de fonction)
(C++20)
génère la prochaine permutation lexicographique inférieure d'une plage d'éléments
(objet fonction algorithme)