Imprimer toutes les permutations de la chaîne en C++
-
Utilisez
std::next_permutationpour imprimer toutes les permutations de la chaîne en C++ -
Utilisez
std::prev_permutationpour imprimer toutes les permutations de la chaîne en C++
Cet article présentera comment imprimer toutes les permutations de la chaîne donnée en C++.
Utilisez std::next_permutation pour imprimer toutes les permutations de la chaîne en C++
L’algorithme std:next_permutation modifie la plage donnée pour que la permutation des éléments soit ordonnée lexicographiquement par ordre croissant, et qu’une vraie valeur booléenne soit renvoyée si une telle permutation existe. La fonction peut opérer sur l’objet std::string pour générer ses permutations si les caractères de la chaîne sont triés par ordre décroissant. Nous pouvons utiliser l’algorithme std::sort avec l’objet fonction std::greater pour trier la chaîne, puis appeler next_permutation jusqu’à ce qu’il renvoie false. Ce dernier peut être implémenté en utilisant la boucle do...while qui prend l’instruction next_permutation comme expression de condition et imprime la chaîne dans le flux cout à chaque cycle.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
using std::cin;
using std::cout;
using std::endl;
using std::string;
void PrintStringPermutations(string &str) {
std::sort(str.begin(), str.end(), std::greater<>());
do {
cout << str << endl;
} while (std::next_permutation(str.begin(), str.end()));
}
int main() {
string input;
cout << "Enter string to print permutations: ";
cin >> input;
PrintStringPermutations(input);
return EXIT_SUCCESS;
}
Production:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
Utilisez std::prev_permutation pour imprimer toutes les permutations de la chaîne en C++
Alternativement, nous pouvons utiliser un autre algorithme de STL appelé - std::prev_permutation qui génère la nouvelle permutation de la plage donnée avec le même ordre lexicographique mais stocke la permutation précédente lorsque la séquence est fournie. La solution finale reste toujours similaire à l’exemple précédent, sauf que la fonction prev_permutation est appelée dans la condition de boucle while.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
using std::cin;
using std::cout;
using std::endl;
using std::string;
void PrintStringPermutations(string &str) {
std::sort(str.begin(), str.end(), std::greater<>());
do {
cout << str << endl;
} while (std::prev_permutation(str.begin(), str.end()));
}
int main() {
string input;
cout << "Enter string to print permutations: ";
cin >> input;
PrintStringPermutations(input);
return EXIT_SUCCESS;
}
Production:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
De plus, on peut garantir un code plus robuste en implémentant la fonction de validation de chaîne utilisateur qui imprimera l’invite de saisie jusqu’à ce que l’utilisateur fournisse la chaîne valide. Notez que toutes les solutions répertoriées n’analyseront que l’argument de chaîne unique de l’entrée de ligne de commande et que les chaînes de plusieurs mots ne seront pas lues.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
using std::cin;
using std::cout;
using std::endl;
using std::string;
void PrintStringPermutations(string &str) {
std::sort(str.begin(), str.end(), std::greater<>());
do {
cout << str << endl;
} while (std::prev_permutation(str.begin(), str.end()));
}
template <typename T>
T &validateInput(T &val) {
while (true) {
cout << "Enter string to print permutations: ";
if (cin >> val) {
break;
} else {
if (cin.eof()) exit(EXIT_SUCCESS);
cout << "Enter string to print permutations\n";
cin.clear();
cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
return val;
}
int main() {
string input;
validateInput(input);
PrintStringPermutations(input);
return EXIT_SUCCESS;
}
Production:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook