find all permutations of a string in c++ [closed]

Question

The following is a code to print all permutations of a given string. The code compiles but does not 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

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

#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()) );
}

Well what does it do? std::next_permutation takes two iterators, one is the beginning of your string, the second is the end, so basically you're saying "consider the whole string". It permutes the string s such that after the call, s contains the unique permutation that would appear in lexicographical order directly after the previous value of s. If s is the last such permutation (i.e. "gfedcba" for input "abcdefg"), std::next_permutation returns false and thus you know you're done.

Since you're not creating any new (temporary) strings with this code, it is not only more readable, but also faster. On my machine, your algorithm takes roughly 5 seconds for "abcdefghij", the one using std::next_permutation finishes in less than a second. With another character it becomes worse to 54sec vs. 6.8sec.

Note that if the initial string isn't sorted, this will not give the complete list of permutations. But of course there is an easy solution for this: Perform std::sort(s.begin(), s.end()); before permuting.

Answer 2

So you are so tantalizingly close. You just want when the empty string is matched as opposed to a 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);