Recursive Permutation Generator

mvmalderen 2 Tallied Votes 1K Views Share

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;