Namespaces
Variants

std:: next_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
next_permutation

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

Permute la plage [ first , last ) en la prochaine permutation . Retourne true si une telle "permutation suivante" existe ; sinon transforme la plage en la première permutation lexicographique (comme avec std::sort ) 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 LegacyBidirectionalIterator .

Valeur de retour

true si la nouvelle permutation est lexicographiquement supérieure à l'ancienne. false si la dernière permutation a été atteinte et que la plage a été réinitialisée à la première permutation.

Complexité

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

1,2) Au maximum
N
2
échanges.

Exceptions

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

Implémentation possible 

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    auto r_first = std::make_reverse_iterator(last);
    auto r_last = std::make_reverse_iterator(first);
    auto left = std::is_sorted_until(r_first, r_last);
    if (left != r_last)
    {
        auto right = std::upper_bound(r_first, left, *left);
        std::iter_swap(left, right);
    }
    std::reverse(left.base(), last);
    return left != r_last;
}

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 trois permutations de la chaîne "aba" .

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

Sortie : 

aba
baa
aab

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 plus petite d'une plage d'éléments
(modèle de fonction)
(C++20)
génère la prochaine permutation lexicographique plus grande d'une plage d'éléments
(objet fonction algorithme)