Stampa tutte le permutazioni della stringa in C++
-
Usa
std::next_permutationper stampare tutte le permutazioni della stringa in C++ -
Usa
std::prev_permutationper stampare tutte le permutazioni della stringa in C++
Questo articolo introdurrà come stampare tutte le permutazioni della stringa data in C++.
Usa std::next_permutation per stampare tutte le permutazioni della stringa in C++
L’algoritmo std:next_permutation modifica l’intervallo dato in modo che la permutazione degli elementi sia ordinata lessicograficamente in ordine crescente e venga restituito un vero valore booleano se tale permutazione esiste. La funzione può operare sull’oggetto std::string per generare le sue permutazioni se i caratteri stringa sono ordinati in ordine decrescente. Possiamo utilizzare l’algoritmo std::sort con l’oggetto funzione std::greater per ordinare la stringa e quindi chiamare next_permutation finché non restituisce false. Quest’ultimo può essere implementato utilizzando il bucle do...while che prende l’istruzione next_permutation come espressione di condizione e stampa la stringa nel flusso cout ad ogni bucle.
#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;
}
Produzione:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
Usa std::prev_permutation per stampare tutte le permutazioni della stringa in C++
In alternativa, possiamo utilizzare un altro algoritmo da STL chiamato - std::prev_permutation che genera la nuova permutazione dell’intervallo dato con lo stesso ordine lessicografico ma memorizza la permutazione precedente quando viene fornita la sequenza. La soluzione finale rimane ancora simile all’esempio precedente, tranne per il fatto che la funzione prev_permutation viene chiamata nella condizione del cicli 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;
}
Produzione:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
Inoltre, è possibile garantire un codice più robusto implementando la funzione di convalida della stringa utente che stamperà il prompt di input finché l’utente non fornirà la stringa valida. Si noti che tutte le soluzioni elencate analizzeranno solo l’argomento a stringa singola dall’input della riga di comando e le stringhe di più parole non verranno lette.
#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;
}
Produzione:
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