std::next_permutation
| 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 permutation suivante. Retourne true si une telle « permutation suivante » existe ; sinon transforme la plage en la première permutation lexicographique (un ordre croissant) et retourne false.
operator<(jusqu’à C++20)std::less{}(depuis C++20).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.
Paramètres
| first, last | - | la paire d’itérateurs définissant la plage d’éléments à permuter |
| comp | - | objet fonction de comparaison (c’est-à-dire un objet satisfaisant les exigences de Compare) qui retourne true si le premier argument est inférieur au second.La signature de la fonction de comparaison doit être équivalente à ce qui suit :
Bien que la signature n’ait pas besoin d’avoir |
| Exigences de type | ||
-BidirIt doit satisfaire les exigences de LegacyBidirectionalIterator.
| ||
Valeur de retour
true si la nouvelle permutation est lexicographiquement plus grande que 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) :
| N |
| 2 |
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 des permutations, les implémentations typiques effectuent environ 3 comparaisons et 1,5 échanges par appel.
Les implémentations (p. ex. 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 une fonction membre spéciale non triviale ni un ADL-trouvé swap.
Exemple
Le code suivant affiche toutes les permutations d’une chaîne.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
int main()
{
std::string s = "ABBA";
std::sort(s.begin(), s.end());
do
std::cout << s << '\n';
while (std::next_permutation(s.begin(), s.end()));
assert(std::is_sorted(s.begin(), s.end()));
}
Sortie :
AABB
ABAB
ABBA
BAAB
BABA
BBAA
Voir aussi
(C++11) |
détermine si une séquence est une permutation d’une autre séquence (modèle de fonction & objet fonction d’algorithme) |
(C++20) |
|
| génère la prochaine permutation lexicographique plus petite d’une plage d’éléments (modèle de fonction & objet fonction d’algorithme) | |
(C++20) |
|
(C++20) |
génère la prochaine permutation lexicographique plus grande d’une plage d’éléments (objet fonction d’algorithme) |