Menu
Why doesn't this simple function output all permutations of the inputted 5 letter string? I think there should be 120 and it only outputs 90.
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; // Creates permutation lists for strings vector<string> createdcombos2(string letters) { vector<string> lettercombos; cout << "Letters are: " << letters << endl; //input string do lettercombos.push_back(letters); while(next_permutation(letters.begin(), letters.end())); cout <<"Letter combos: " << endl; //print out permutations for (auto i : lettercombos) cout << i << endl; cout << endl << lettercombos.size() << endl; //number of permutations return lettercombos; } int main() { string letters = "gnary"; vector<string> lettercombos; lettercombos = createdcombos2(letters); } 
433
Next_permutation transforms the range of elements [first, last) into the lexicographically next greater permutation of the elements. […] If such a permutation exists, next_permutation transforms [first, last) into that permutation and returns true.
std::next_permutation Different permutations can be ordered according to how they compare lexicographically to each other. The complexity of the code is O(n*n!)
C++ Algorithm next_permutation() function is used to reorder the elements in the range [first, last) into the next lexicographically greater permutation. A permutation is specified as each of several possible ways in which a set or number of things can be ordered or arranged. It is denoted as N!
The lexicographically next permutation is basically the greater permutation. For example, the next of “ACB” will be “BAC”. In some cases, the lexicographically next permutation is not present, like “BBB” or “DCBA” etc. In C++ we can do it by using a library function called next_permutation().
To return all permutations in a loop until next_permutation returns false, the vector must be sorted before the start of the loop. next_permutation returns the permutations in ascending order. So if you start off with an unsorted vector, it will begin part way through the series of permutations.
std::sort(letters.begin(), letters.end()); do lettercombos.push_back(letters); while(next_permutation(letters.begin(), letters.end())); If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
