Can someone explain why this recursive call works?

[voidStream]

The program prints the permutations of a string. I was wondering why it works just the part where you swap the first two letters and why this works in a broad case as well i.e string of length > 3.



#include<iostream>
#include<string>
using namespace std;

void permutate(string x, int pos);
int main() {

string input;
cout << "Enter something: \n";
cin >> input;

permutate(input, 0);

return 0;
}

void permutate(string x, int pos){

if(pos == x.length()-1){
return;
}
for(int i=0; i < x.length()-1; i++){
std::swap(x.at(i), x.at(i+1));
cout << x << endl;
permutate(x, pos+1);
}
}

[Smac89]

Wouldn't this function print duplicates as well?

Why does a recursive call work? Because the program hasn't run out of stack space.

The way this program works is beautifully lazy in the fact that there is no real algorithm to it. It just lazily generates a bunch of substrings of the given string and hopes that by the time the brute force method ends, it has generated enough substrings that all the permutations of the string have also been generated.
The swapping part is indeed the best part of this program because it just simply swaps the 2 adjacent characters in the string thus generating a new string and then recursively visits that string. In graph terms we will call this depth first search.

So as to why it works? It doesn't. It just does a lot of work and hopes for the best which in this case being that all the permutations have been found. If you want a challenge, take a look at std::next_permutation and try to write a function that does the same thing. std::next_permutation is a standard library function that generates permutations of a given range in the lexicographical order imposed by the weak ordering of the values.

[voidStream]

Why do you say that it does not work though? Doesnt it print the correct answer for any string given. Also wouldnt this be the most efficent way to permute a string?

[Smac89]

When I say it doesn't work, I am not trying to imply that the function will not print all permutations (it will infact). What I'm saying is that the function is so simple in it's implementation that when compared to other methods of generating permutations, this one will be considered the laziest of the bunch i.e. it's implementation is a lot simpler than most.

Efficiency can be described in different ways,

In terms of time, we could consider the algorithm to be O(N) since the duplicates it prints aren't large enough, so it is efficient with respect to time

If you are wanting to only get the next permutation of a given string, then this algorithm is inefficient because you will not get just the next permutation, but all permutations. So in this sense it is inefficient

If the aim is to get just the permutations of a given string or to get them in lexicographic order, this algorithm is again inefficient because it will give you duplicates as well as not print things in order