The string permutation problem aims to find all the permutations of a string(re-arrangement of characters in this string). A string of length n has n! permutations.

The essence of string permutation is recursively swapping each letter with other letters in this string. Following image shows the permutation of string “ABC”. For each step, fix the left part of the string, and swap two letters in the right part, until there is no letters left in the right part.

</img>

Based on above strategy, the following two recusive algorithm could be implemented.

Algorithm 1(Reference: Write a C program to print all permutations of a given string):

void StrPermute(string& str, vector<string>& vec, int i) {
	if(i==str.length())
		vec.push_back(str);
	else {
		for(int j=i;j<str.size();++j) {
			std::swap(str[i],str[j]);
			StrPermute(str,vec,i+1);
			std::swap(str[i],str[j]);
		}
	} // end if
}

Algorithm 2(Reference: Find all the permutations of a string in Java):

void StrPermute(vector<string>& vec, string prefix, string str) {
	//cout<<"prefix="<<prefix<<", str="<<str<<endl; // TEST ONLY
	int n=str.length();
	if(n==0)
		vec.push_back(prefix);
	else {
		for(int j=0;j<n;++j)
			StrPermute(vec,prefix+str[j],str.substr(0,j)+str.substr(j+1));
	} // end if
}

The permuted strings are stored as a vector of string. For both algorithms, the time complexities are O(n*n!).