Implémenter la permutation complète C++ d'une chaîne donnée à l'aide de STL

Une permutation de la chaîne est formée lorsque les caractères d'une chaîne donnée sont réorganisés sous n'importe quelle forme. Par exemple, dans ce tutoriel, nous verrons comment imprimer toutes les permutations d'une chaîne donnée à l'aide de la bibliothèque de modèles standard de C++

Input : s = “ADT” Output : “ADT”, “ATD”, “DAT”, “DTA”, “TAD”, “TDA” Explanation : In the given output as you can see all the string are made up of same three character present in our string and are just rearranged thus they fit in the definition of a permutation of a string now there is one more thing to note these are all the permutations possible of string s.

Il existe deux façons d'imprimer toutes les permutations d'une chaîne donnée

Rotate()

Nous sommes aller à La première méthode utilisée consiste à utiliser la méthode de rotation. Dans cette méthode, nous utiliserons la fonction de rotation de STL, qui est utilisée pour faire pivoter les chaînes, et nous utiliserons la récursivité pour imprimer l'arrangement.

Exemple

Code C++ pour la méthode ci-dessus

#include using namespace std; void permutations(string s, string ans){ if(s.size() == 0) { // when our string which needs to //be rotated becomes empty then it means //that our permutation is stored in ans cout << ans << "\n"; return ; } for(int i = 0; i < s.size(); i++){ permutations(s.substr(1), ans + s[0]); // we are adding the // first character in our ans // passing all elements from index 1 in our // rotate string for next function. rotate(s.begin(), s.begin()+1, s.end()); //rotating such that our second element becomes first } } int main(){ string s = "ADT"; // given string permutations(s, ""); return 0; }

Output

ADT ATD DTA DAT TAD TDA

Next_Permutation

Maintenant, nous allons utiliser une autre fonction de STL, next_Permutation, comme son nom l'indique, la valeur de retour de cette fonction est la prochaine permutation de la chaîne existe. Sinon, renvoie false.

Comme vous le savez, cette fonction vérifie la permutation suivante ; nous devons donc d'abord trier la chaîne lexicographiquement afin d'obtenir toutes les permutations possibles.

Exemple

Code C++ pour la méthode ci-dessus

#include using namespace std; int main(){ string s = "ADT"; // given string sort(s.begin(), s.end()); // sorting the string do{ cout << s << "\n"; // printing the permutations }while(next_permutation(s.begin(), s.end())); // till next_permutations returns false return 0; }

Output

ADT ATD DAT DTA TAD TDA

Dans le programme ci-dessus, nous trions la chaîne puis, à l'aide de la fonction next_permutation, nous imprimons toutes les permutations possibles.

Conclusion

Dans ce tutoriel, nous avons imprimé toutes les permutations possibles d'une chaîne donnée à l'aide de STL en C++. Nous avons également appris le programme C++ pour le problème ainsi que quelques fonctions STL de base et leur utilisation. Nous espérons que vous avez trouvé ce tutoriel utile.

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!