Une permutation de longueur n est une collection ordonnée sans répétitions des nombres 1, 2, ..., n. Par exemple, [3, 1, 2] et [5, 4, 3, 2, 1] sont des permutations, mais [1, 2, 1, 3] et [1, 2, 4] ne le sont pas.
Si la tâche est réduite au fait qu'il est nécessaire d'itérer sur toutes les permutations de longueur n, vous pouvez utiliser un mécanisme pratique en C ++, appelé "next_permutation".
Vous pouvez en savoir plus à ce sujet dans la documentation, mais le fait est que cette fonction modifie le tableau passé à la permutation ultérieure dans l'ordre lexicographique (qui est généralement clair et son nom).
Pour utiliser next_permutation, vous devez inclure la bibliothèque d'algorithmes (c'est-à-dire écrire #include <algorithm> au début du programme)
Exemples:
vecteur arr ;
arr = { 1, 2, 3 } ; // le tableau est [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // passe le tableau entier à la fonction
// le tableau est maintenant [1, 3, 2]
arr = { 2, 3, 1 } ; // le tableau est [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // passe le tableau entier à la fonction
// le tableau est maintenant [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // il est possible d'appliquer une fonction à une partie d'un tableau, mais en pratique c'est rarement nécessaire
// le tableau est maintenant [3, 2, 1]
Dans ce cas, la fonction a une valeur de retour booléenne qui est vraie si la permutation suivante a été générée et fausse s'il n'y en a pas eu de suivante (cas où la permutation maximale dans l'ordre lexicographique est passée à la fonction).
Cela permet d'utiliser la fonction dans une boucle, ce qui nous permettra d'itérer sur toutes les permutations à la fois. En raison de l'indexation à 0, en pratique, il est souvent plus pratique de travailler avec une permutation de nombres de 0 à n - 1, bien qu'une permutation contienne formellement des nombres de 1 à n. Mais heureusement, cela n'entraîne pas de superpositions supplémentaires dans le code, car la fonction next_permutation est adaptée aux permutations indexées à 0 (et même aux éléments dupliqués dans un tableau, mais vous pouvez en savoir plus par vous-même).
En général, le code d'itération sur toutes les permutations ressemble à ceci :
international ; // taille de la permutation
vecteurperm(n); // perm est l'abréviation de "permutation", c'est-à-dire "permutation"
pour (int je = 0; je < n; je++)
perm[je] = je ; // initialise la permutation initiale 0, 1, ..., n - 1
faire {
// à l'intérieur de la boucle, nous traitons la permutation actuelle
} while (next_permutation(perm.begin(), perm.end())); // s'il n'y a pas de permutation suivante, alors termine la boucle
Ce code s'exécute en O(n! * f(n)), où f(n) est le temps qu'il vous faut pour traiter une permutation particulière.