Imprimir todas as permutações da string em C++
-
Use
std::next_permutationpara imprimir todas as permutações da string em C++ -
Use
std::prev_permutationpara imprimir todas as permutações da string em C++
Este artigo irá apresentar como imprimir todas as permutações da string fornecida em C++.
Use std::next_permutation para imprimir todas as permutações da string em C++
O algoritmo std:next_permutation modifica o intervalo dado para que a permutação dos elementos seja ordenada lexicograficamente em ordem crescente, e um valor booleano verdadeiro é retornado se tal permutação existir. A função pode operar no objeto std::string para gerar suas permutações se os caracteres da string forem classificados em ordem decrescente. Podemos utilizar o algoritmo std::sort com o objeto de função std::greater para ordenar a string e então chamar next_permutation até retornar falso. O último pode ser implementado usando o loop do...while que pega a instrução next_permutation como a expressão de condição e imprime a string no fluxo cout a cada 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;
}
Resultado:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
Use std::prev_permutation para imprimir todas as permutações da string em C++
Alternativamente, podemos utilizar outro algoritmo de STL chamado - std::prev_permutation que gera a nova permutação do intervalo dado com a mesma ordem lexicográfica, mas armazena a permutação anterior quando a sequência é fornecida. A solução final ainda permanece semelhante ao exemplo anterior, exceto que a função prev_permutation é chamada na condição de loop 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;
}
Resultado:
Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
Além disso, pode-se garantir um código mais robusto implementando a função de validação de string do usuário que imprimirá o prompt de entrada até que o usuário forneça a string válida. Observe que todas as soluções listadas analisarão apenas o argumento da string única da entrada da linha de comando, e as strings com várias palavras não serão lidas.
#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;
}
Resultado:
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