Find all line permutations in C ++

Question

Below is the code for printing all permutations of a given string. The code compiles but doesn't print anything.

using namespace std; void RecPermute(string, string); int main() { RecPermute("", "abc"); return 0; } void RecPermute(string soFar, string rest) { if (rest == " ") { cout << soFar << endl; } else { for(int i=0; i<rest.length(); i++) { string next = soFar + rest[i]; string remaining = rest.substr(0, i) + rest.substr(i+1); RecPermute(next, remaining); } } } 

What needs to be fixed?

Answer 1

So you are so painfully close. You just want the empty string to be matched, not the space. You can do this by matching the empty string "" .

Change

 if (rest == " ") { ... } 

to

 if (rest == "") { ... } 

and you forgot the length of rest.substr (i + 1), it should be (i + 1, i-3);

Answer 2

Your approach works (with the correct condition provided by greedybuddha), but can be achieved much easier (as Chris suggested).

 #include <algorithm> #include <iostream> #include <string> int main() { std::string s("abcdefg"); do { std::cout << s << "\n"; } while ( std::next_permutation(s.begin(), s.end()) ); } 

OK, what is he doing? std::next_permutation takes two iterators, one the beginning of your line, the second the end, so basically you say “look at the whole line”. It permutes the string s in such a way that after the call, s contains a unique permutation, which will be displayed in lexicographic order immediately after the previous value of s . If s is the last such permutation (that is, "Gfedcba" to enter "abcdefg"), std::next_permutation returns false and, therefore, you know that everything is ready.

Since you are not creating any new (temporary) lines with this code, this is not only more readable, but faster. On my machine, your algorithm takes about 5 seconds for "abcdefghij", the one that uses std::next_permutation ends in less than a second. With another character, he gets worse than 54 seconds versus 6.8 seconds.

Note that if the original row is not sorted, this will not give a complete list of permutations. But, of course, there is a simple solution for this: Run std::sort(s.begin(), s.end()); before rearrangement.