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

CKTIS / C++

std::next_permutation — permutation lexicographique suivante

std::next_permutation réorganise une plage selon sa permutation lexicographique suivante. La fonction renvoie true si une permutation suivante existe ; après la dernière, elle rétablit la première disposition et renvoie false.

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

Syntaxe

#include <algorithm>

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

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

std::next_permutation, définie dans <algorithm>, modifie directement la plage [first, last). L’ordre lexicographique de deux dispositions est déterminé par la première position où leurs éléments ne sont pas équivalents selon la comparaison utilisée. La surcharge sans comp utilise la comparaison « inférieur à » par défaut ; celle avec comp définit l’ordre à l’aide de ce comparateur.

Un résultat true signifie qu’une permutation suivante a été trouvée. Un résultat false ne signifie pas que les données sont restées inchangées : l’algorithme rétablit la première disposition, triée dans l’ordre croissant selon la comparaison choisie. Une plage vide ou ne contenant qu’un élément renvoie false.

Les itérateurs doivent être bidirectionnels et les éléments qu’ils désignent doivent permettre l’échange de valeurs. comp doit définir un ordre faible strict ; n’utilisez pas <=. Pour N éléments, la norme limite le nombre d’échanges à N / 2.

Commencez par une plage triée selon la même comparaison et utilisez do–while pour traiter aussi la disposition initiale. La boucle parcourt une disposition pour chaque séquence distincte de classes d’équivalence définies par la comparaison. Si la comparaison considère des valeurs différentes comme équivalentes, la boucle peut omettre certaines séquences de valeurs distinctes. Dans l’exemple, la comparaison par défaut distingue 1 de 2 : la boucle affiche donc les trois dispositions distinctes des valeurs. L’exemple montre aussi l’état après l’appel final qui renvoie false.

Exemples

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

int main() {
    std::array<int, 3> values{1, 1, 2};
    do {
        std::cout << values[0] << ' ' << values[1] << ' '
                  << values[2] << '\n';
    } while (std::next_permutation(values.begin(), values.end()));

    std::cout << "reset: " << values[0] << ' ' << values[1]
              << ' ' << values[2] << '\n';
}

Résultat

1 1 2
1 2 1
2 1 1
reset: 1 1 2

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