Recursive Permutation Generator

By Mathias Van Malderen on Feb 19th, 2010 4:42 pm

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.

#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[0];
    s[0] = 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[0] + 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;
}

This article has been dead for over three months

You