Recursive Permutation Generator

mvmalderen 2 1K Views

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;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview