Comment fonctionne l'algorithme std::next_permutation pour trouver la prochaine permutation lexicographiquement plus grande d'une séquence ?

std::next_permutation Explication de l'implémentation

L'algorithme std::next_permutation calcule la prochaine permutation lexicographiquement plus grande d'une séquence donnée. Comprendre sa mise en œuvre 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 un 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 ascendant.

Loop Flow

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érez la séquence {1, 2, 4, 3} .

• Itération 1 : i est initialement à 3. j est à 2. Depuis 3 < 4 (i < j), i est un ascendant.
• 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é. je suis maintenant à 2. j est à 1. 2 &Lt ; 3, donc i est un ascendant.
• 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}.

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!