# Recursive Permutation Generator

Some things you need to know:

• This code is not efficient, if you want a more efficient solution, then turn to the STL algorithm next_permutation.
• When there are double characters (i.e. characters which occur multiple times) in the string to permute then some permutations will be generated multiple times.
• As this function will generate all permutations and since the factorial of the string length grows very quickly, you should make sure that you don't pass a string containing too much characters, you know: it could take years to complete, and this is probably not what you want.
874 Views
About the Author

Just check out [my thread](http://www.daniweb.com/community-center/community-introductions/threads/205430/hello-from-tux) in the community introductions if you want to know more about me.

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

/**
Generate lexical permutations of a string by using recursion
@param s string of which the lexical permutations will be generated
@return a vector holding all lexical permutations of the string parameter s
*/
vector<string> getPermutations(string s)
{
vector<string> permutations;

if ( s.length() == 1 )
{
// Store the permutations of the simplest case
permutations.push_back( s );
return permutations;
}

for (size_t i=0; i < s.length(); i++)
{
// Swap values
char c;
c = s;
s = s[i];
s[i] = c;

// Generate sub-permutations
vector<string> subPermutations;
subPermutations = getPermutations( s.substr(1) );

// Build the whole permutations, and store them
for (size_t j=0; j < subPermutations.size(); j++)
{
permutations.push_back( s + subPermutations[j] );
}
}

return permutations;
}

int main()
{
vector<string> p;
p = getPermutations("123");

for (size_t i=0; i < p.size(); i++)
cout << p[i] << endl;
}``````