Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

std::prev_permutation — permutation lexicographique précédente

std::prev_permutation réorganise une plage selon sa permutation lexicographique précédente. Elle renvoie bool ; si aucune permutation précédente n’existe, elle réorganise la plage selon la dernière permutation et renvoie false.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

#include <algorithm>

template<class BidirectionalIterator>
constexpr bool prev_permutation(BidirectionalIterator first,
                                BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
constexpr bool prev_permutation(BidirectionalIterator first,
                                BidirectionalIterator last,
                                Compare comp);

std::prev_permutation, déclarée dans <algorithm>, modifie [first, last) sur place pour produire l’arrangement immédiatement précédent dans l’ordre lexicographique. L’ordre est déterminé par la première position où les valeurs ne sont pas équivalentes selon le comparateur. En C++23, le comparateur par défaut est std::less{}, qui garantit un ordre total strict sur les pointeurs même lorsque l’opérateur intégré < ne le garantit pas. La surcharge qui prend comp permet de fournir un autre ordre faible strict.

Une valeur de retour true signifie qu’une permutation précédente a été trouvée. Une valeur de retour false ne signifie pas que les données sont restées inchangées : l’algorithme produit la dernière permutation, en ordre décroissant selon l’ordre choisi. Pour une plage vide ou contenant un seul élément, il renvoie false et le contenu reste identique.

L’algorithme exige des itérateurs bidirectionnels dont les valeurs référencées peuvent être échangées. Il n’est pas nécessaire de trier les données avant d’effectuer un seul pas. Si le comparateur distingue toute paire de valeurs distinctes dans la plage, partez d’un arrangement décroissant et utilisez une boucle do–while pour parcourir chaque arrangement distinct des valeurs exactement une fois, du plus grand au plus petit. Si des valeurs distinctes sont équivalentes selon le comparateur, l’algorithme ne distingue que les arrangements de leurs classes d’équivalence et peut donc passer certains arrangements de valeurs. Par exemple, si la plage ne contient que deux valeurs distinctes que le comparateur considère comme équivalentes, le premier appel renvoie déjà false.

L’exemple montre les transitions entre permutations ainsi que le retour à la dernière permutation après false. Cette entrée décrit les surcharges de std::prev_permutation qui renvoient bool, et non l’interface std::ranges.

Exemples

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    std::array<int, 3> values{2, 1, 1};
    std::cout << std::boolalpha;

    bool found;
    do {
        for (int value : values) {
            std::cout << value;
        }
        found = std::prev_permutation(values.begin(), values.end());
        std::cout << " -> " << found << '\n';
    } while (found);

    std::cout << "after wrap: ";
    for (int value : values) {
        std::cout << value;
    }
    std::cout << '\n';
}

Résultat

211 -> true
121 -> true
112 -> false
after wrap: 211

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources