Permutation algorithm

Question

I was asked to write a permutation algorithm to find the permutations of {a,b,c}. Since this is a famous question to which an answer is readily available online, I wanted to do it a little differently, so that it won't look like I copied off the Internet. It was evaluated as OK for the algorithm being correct, but said that the algorithm is inefficient and also there are 'major concerns' in the code.

I would really appreciate if the experts here would advice me on what is wrong about this code, so that I can learn and fix my mistakes. I understand that the use of templates is an overkill, but other than that, what is so wrong about this code? The question was, find the permutations of {a,b,c}.

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

template<typename T> vector<T> TruncateVector(vector<T>, int);
template<typename T> vector<vector<T> > GetPerms(vector<T>);
unsigned GetNumPerms(unsigned);
template<typename T>
bool ValidatePermutations(vector<T>, vector<vector<T> >);


int main()
{
       // Create a vector with the elements required to permute
       vector<char> permSet;
       permSet.push_back('a');
       permSet.push_back('b');
       permSet.push_back('c');

       // Get the permutations
       vector<vector<char> > vectorOfPerms = GetPerms(permSet);              


       /* Printing the permutations */
       for(unsigned x=0, counter=1;x<vectorOfPerms.size(); x++)
       {
           cout << "(" << counter << ") ";
           for(unsigned y=0;y<vectorOfPerms[x].size(); y++)
           {
               cout << vectorOfPerms[x].at(y) << ' ';
           }
           counter++;
           cout << endl;
       }

       // Validate the calculated permutations
       // This validation only valid for sets with lexicographic order. See notes in the function.
       bool validation = ValidatePermutations(permSet,vectorOfPerms);

       return 0;
}


template<typename T>
vector<vector<T> > GetPerms(vector<T> permSet)
{
   /* --------------- Permutation algorithm -----------------
    * In this algorithm permutations are calculated by sequentially taking each element in the vector,
    * and then combining it with 'all' the permutations of the rest of the vector elements.
    * Example:
    * GetPerms('a,b,c') --> ( {a, GetPerms('b,c')}, {b, GetPerms('a,c')}, {c, GetPerms('a,b')} }
    * The resultant permutations are returned as a vector of vectors, with each vector consisting of one permutation.
    *
    * Vectors were chosen to store the elements because of its ease of handling (inserting, deleting) and also for its ability
    * to handle different types of data.
    */
   vector<vector<T> > vectorOfPerms(GetNumPerms(permSet.size()));
   unsigned PermCount=0;

   if(permSet.size() == 1)  // Base case. Only one element. Return it back.
   {
       vectorOfPerms[0].push_back(permSet.at(0));
   }
   else
   {
       for(unsigned idx=0; idx<permSet.size(); idx++)
       {          
           vector<T> vectorToPermutate = RemoveElement(permSet, idx);   // Remove the current element being combined to permutations.
           vector<vector<T> > PermVector = GetPerms(vectorToPermutate);  // Get the permutations for the rest of the elements.

           // Combine with the received permutations
           for(unsigned count=0 ; count<PermVector.size(); count++, PermCount++)
           {
               vectorOfPerms[PermCount].push_back(permSet.at(idx));    // Insert the first element
               vectorOfPerms[PermCount].insert(vectorOfPerms[PermCount].begin()+1, PermVector[count].begin(), PermVector[count].end());      // Insert the permutations
           }
       }
   }
   return vectorOfPerms;
}


/*
* This function removes the element at index from the vector permSet
*/
template<typename T>
vector<T> RemoveElement(vector<T> permSet, int index)
{
   permSet.erase(permSet.begin()+index);
   return permSet;
}


/*
* This function returns the number of possible permutations for a given
* number of elements
*/
unsigned GetNumPerms(unsigned numElems) {
 return (numElems == 1 ? numElems : numElems*GetNumPerms(numElems - 1));
}


/*
* This function validates the calculated permutations with the std::next_permutation
* IMPORTANT: This validation will only work if the elements are different and inserted in lexicographic order.
* I.e. {a,b,c} will be correctly validated, but not {a,c,b}.
* The permutations generated are CORRECT. Only the validation with std::next_permutation will not be correct.
* This validation was chosen to validate the program for the given question of finding permutations of {a,b,c}.
*/
template<typename T>
bool ValidatePermutations(vector<T> permSet, vector<vector<T> > result)
{
 bool validationResult = true;

 /* Validating the calculated permutations with the std::next_permutation
  * Since std::next_permutation gives the next lexicographically greater permutation with each call,
  * it must match with the permutations generated in GetPerms() function.
  */
 if(result.size() != GetNumPerms(permSet.size()))
 {
     cout << "Number of permutations is incorrect." << endl;
 }
 else
 {
     // Compare element by element
     for(unsigned permCount=0; permCount<result.size(); permCount++)
     {
         for(unsigned elemCount=0; elemCount<permSet.size(); elemCount++)
         {
             if(result[permCount].at(elemCount) != permSet.at(elemCount))
             {
                 validationResult = false;
                 break;
             }
         }

         if(!validationResult)
         {
             break;
         }
         else
         {
             next_permutation(permSet.begin(),permSet.end());
         }
     }
 }

 cout << "Number of elements: " << permSet.size() << endl;
 cout << "Number of permutations: " << result.size() << endl;
 if(validationResult)
 {
     cout << "Validation: " << "PASS" << endl;
 }
 else
 {
     cout << "Validation: " << "FAIL" << endl;
 }

 return validationResult;
}

Answer 1

• Prefer the preincrement operator (++variable) in place of the postincrement operator (variable++).

• Prefer range based for loops or std::for_each so that you can allow the compiler to handle container bounds checking for you. The compiler will be more efficient at this than you can, and can potentially perform loop unrolling especially in the case of std::for_each.

• Prefer to use std algorithms over writing your own for loops. std::find_if or std::any_of are good for finding elements in a container that match a condition. std::generate and std::transform are good for filling a container with values from a function or another container.

• Instead of:

  // Create a vector with the elements required to permute
  vector<char> permSet;
  permSet.push_back('a');
  permSet.push_back('b');
  permSet.push_back('c');
  

• Prefer to initialize directly using uniform initialization such as:

  vector<char> permSet{'a', 'b', 'c'};
  

  Or better yet (if you know that you won't modify permSet):

  const vector<char> permSet{'a', 'b', 'c'};
  

Answer 2

you pre generate all permutations, this means that when you have 20 elements you have 20! = 2.432902e+18 possible permutations all needing to reside in memory when the algorithm finishes

then you copy all vectors over and over, also not a good idea as that requires a lot of memory allocations and deletes

Answer 3

You asked about programming style. I am big fan of reducing things to as simple as possible, with clear names and strong types, and getting things down to the one definition rule as much as possible. There are multiple reasons to prefer simplicity: if you can read it, you can see that it's correct. And it can help make future maintenance activities easier and safer, especially if they're not done by you.

So let's see what happens when I play with your main as an example. I'll go way over the top and define and strongly type everything.

typedef char PERMUTATION_TYPE;
typedef vector<PERMUTATION_TYPE> PERMUTATION_SET;
typedef vector<PERMUTATION_SET> PERMUTATION_SETS;
typedef PERMUTATION_SETS::const_iterator PERMUTATION_SETS_IT;

void printElement(const PERMUTATION_TYPE &element)
{
  cout << element << ' ';
}

void printPermutation (const PERMUTATION_SET &perm)
{
  for_each(perm.begin(), perm.end(), printElement);
  cout << endl;

}

void printIndexedPermutation (const unsigned int permIndex, const PERMUTATION_SET &perm)
{
  cout << "(" << permIndex << ") " ;
  printPermutation(perm);
}


void printPermutationCollection(const PERMUTATION_SETS &permSet)
{
  for (PERMUTATION_SETS_IT perm=permSet.begin(); perm!= permSet.end(); ++perm)
  {
    printIndexedPermutation(distance(permSet.begin(), perm), *perm);
  }
}

void fillPermutationSetWithTestData(PERMUTATION_SET &permSet)
{
  permSet.push_back('a');
  permSet.push_back('b');
  permSet.push_back('c');
}

int main()
{
  PERMUTATION_SET permSet;
  fillPermutationSetWithTestData(permSet);

  PERMUTATION_SETS vectorOfPerms = GetPerms(permSet);              

  printPermutationCollection(vectorOfPerms);

  ValidatePermutations(permSet,vectorOfPerms);

  return 0;
}

So every routine is tiny. main() is now readable without comments. Since you were using std::collections, I got rid of the for loops that used indices, and used iterators instead. Every routine is as simple as possible. Yes, there are a lot of them, but they don't cost you anything. And they're all dead simple.

Of course that led to an issue of printing the index number. If I didn't need the index number, I'd get rid of printIndexedPermutation completely, and have only this one line inside printPermutationCollection():

  for_each(permSet.begin(), permSet.end(), printPermutation);

Would I recommend you go this far with your code? It all depends on what you're trying to do, if you're trying to maintain the routine into the distant future, or if it's just throwaway code. But I also have a lot of experience that suggesgts that throwaway code has a nasty habit of sticking around for a lot longer than I ever intended.

Answer 4

Surely, this is what arrays are for

Read the input into an array of strings, permute a tuple of integer indices, and print out the same string array in the order of the permuted integer tuple.

Apart from input and output no string operations whatsoever ! Also works for any Object type - so for the greatest generality code for an abstract base class, and late bind to String or whatever is required, less coding and more uses. One of the reasons for Object Oriented Programming: Polymorphism in this case a polymorphic algorithm.

Answer 5

The permutations of {a, b, c} are {a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b} and {c, b, a}.

That's the best solution to the question as stated, though I suppose it's likely a more general method is also wanted.

---

Your solution is recursive and does a lot of allocation. A much more effective way would be to make a next_permutation function using this Wikipedia section, either generating them lexicographically or by some more efficient method.