Comment std::next_permutation trouve-t-il la prochaine permutation lexicographiquement plus grande ?

Comment fonctionne std::next_permutation

std::next_permutation est une fonction de la bibliothèque de modèles standard C (STL) qui réorganise une séquence dans la prochaine permutation lexicographiquement plus grande. Pour comprendre sa mise en œuvre, il est utile de visualiser la séquence sous la forme d'un nombre où chaque élément représente un chiffre.

Core Logic

L'algorithme fonctionne selon les principes suivants :

• Trouver le pivot : En partant de la fin de la séquence, il localise le premier élément (i) qui est inférieur à l'élément à sa droite (j). Cela indique que les chiffres à droite de i sont dans l'ordre décroissant.
• Échanger et inverser : Une fois i trouvé, il recherche à partir de la fin le premier élément (k) qui est plus grand que moi. Cet élément est remplacé par i, en le plaçant au premier plan. Les éléments restants à droite de j (de j à la fin) sont ensuite inversés.
• Incrémentez le Pivot : Si un pivot est trouvé (i n'est pas le début), le processus se répète en décrémentant i et j.
• Inverser et quitter : Si un pivot ne peut pas être trouvé (i est le début), la séquence est inversée et la fonction renvoie false, indiquant qu'il n'y a plus de permutations sont possibles.

Variables dans le code

• i : Représente l'élément pivot le plus à gauche.
• j : Représente l'élément à droite de i qui est inférieur à i.
• k : Représente l'élément de droite qui est supérieur à i et sera être échangé avec i.

Exemple

Considérez la séquence : 1, 3, 2, 4.

• Trouver le pivot : i est initialement fixé à 4, mais comme 4 est supérieur ou égal à 2, on passe à i = 2. Puisque 2 est inférieur à 4, i est le pivot.
• Échanger et inverser : j est défini sur 3 et k est défini sur 1, qui est le premier élément en partant de la droite qui est supérieur à 2. 1 est échangé avec 2, ce qui donne 1, 2, 3 , 4. Les éléments restants de j à la fin (2, 3, 4) sont inversés, donnant 1, 2, 4, 3.
• Incrémentez le Pivot : i est décrémenté à 1 (j est déjà réglé sur 2). Puisque 1 est inférieur à 2, le processus se répète.
• Trouver le pivot : i est décrémenté jusqu'au premier élément (début), indiquant qu'un pivot est introuvable.
• Inverser et quitter : La séquence est inversée à son état d'origine 1, 2, 3, 4 et la fonction renvoie false, indiquant qu'aucune autre permutation n'est possible.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!