std::next_permutation Implémentation Explication

L'algorithme std::next_permutation calcule la prochaine permutation lexicographiquement plus grande d'une séquence donnée. Comprendre son implémentation est crucial pour comprendre son comportement.

Aperçu de l'algorithme

L'algorithme parcourt la séquence de droite à gauche, à la recherche de l'"ascendant" le plus à gauche (c'est-à-dire , un élément plus petit que son successeur). Si aucun ascendant n'est trouvé, cela signifie que la séquence est par ordre décroissant, auquel cas il inverse la séquence pour obtenir la plus petite permutation.

Sinon, l'algorithme continue en trouvant le plus petit élément de la séquence à droite. de l'ascendeur (appelé "k"). Cet élément est ensuite échangé avec l'ascendeur. Enfin, les éléments à droite de l'ascendeur sont inversés pour maintenir l'ordre décroissant.

Rôles variables

• i : Pointe vers l'élément actuel en cours d'examen.
• j: Pointe vers l'élément immédiatement avant i.
• k: Pointe vers le plus petit élément de la séquence à droite de i lorsque i est un ascendant.

Flux de boucle

La boucle itère jusqu'à ce que i atteigne le début de la séquence (début). Au sein de chaque itération :

1. Si i n'est pas un ascendant, il décrémente i et j.
2. Si i est un ascendant, il trouve le plus petit élément à droite de i (k ), l'échange avec i et inverse tout à droite de i.

Exemple

Considérons la séquence {1, 2, 4, 3} .

• Itération 1 : i est initialement à 3. j est à 2. Puisque 3
• Itération 2 : k s'avère être 2. 3 est échangé avec 2. {1, 3, 4, 2}. Les éléments à droite de 3 (4 et 2) sont inversés. {1, 3, 2, 4}.
• Itération 3 : i est décrémenté et j est décrémenté. i est maintenant à 2. j est à 1. 2
• Itération 4 : k s'avère être 1. 2 est échangé avec 1. { 1, 2, 4, 3}. Les éléments à droite de 2 (4 et 3) sont inversés. {1, 2, 3, 4}.
• Itération 5 : i est décrémenté et j est décrémenté. i est maintenant à 1. j est au début de la séquence. Puisqu’il n’y a plus d’ascendeurs, la séquence est inversée. {4, 3, 2, 1}.