Implementing Permutation Variations

• Download source files - 5.13 Kb

Introduction

As each programmer must have experienced, often you can modify a function only a little to meet the new requirement. Here I present such an example for permutation -- to enumerate all element arrangements for an ascending ordered list. For instance, for a string �abc� where 'a'<'b'<'c', we have permutations �abc�, �acb�, �bac�, �bca�, �cab�, and �cba�, while for a half ordered �cab�, the result is �cab� and �cba�. The following function picked from the STL header file �algorithm� shows how to generate the next permutation from the previous one.

template<class _BidIt> inline
bool next_permutation(_BidIt _First, _BidIt _Last)
{   
   _BidIt _Next = _Last;
   if (_First ==_Last || _First == --_Next) return (false);

   for (; ; )
   {   
      // find rightmost element smaller than successor

      _BidIt _Next1 = _Next;
      if (*--_Next < *_Next1)      
      {   // swap with rightmost element that's smaller

         _BidIt _Mid = _Last;
         for (; !(*_Next < *--_Mid);) ;

         std::iter_swap(_Next, _Mid);
         std::reverse(_Next1, _Last);   
         return (true);
      }

      if (_Next == _First)
      {   // pure descending, flip all

         std::reverse(_First, _Last);
         return (false);
      }
   }
}

To obtain all permutations, just set a loop like this:

   do v.insert(v.end(), s);
   while (next_permutation(s.begin(), s.end()));

Where s is a work string for character permutation and v is a vector to collect permuted s iteratively. In practice, we may meet some permutation variations, two of which are then discussed in this article.

With Non-Ordered Elements

First, consider a permutation variation in a list without a predicate defined for element comparison, in other words, a list without intrinsic order. So, the algorithm cannot rely on the comparisons by the �less than� operator �<� in next_permutation(). For example, either from string �abc� or �cab�, we always want all six permutations as mentioned above.

For this, I adapt the STL function to _next_permutation() by adding the third �map� parameter as shown in the following:

template<class _BidIt> inline
bool _next_permutation(_BidIt _First, _BidIt _Last, Position_Map* pMap/*=NULL*/)
{   
   _BidIt _Next = _Last;
   if (_First ==_Last || _First == --_Next) return (false);

   for (; ; )
   {   
      _BidIt _Next1 = _Next;
      if (pMap? (*pMap)[*--_Next] < (*pMap)[*_Next1]: *--_Next < *_Next1)      
      {   
         _BidIt _Mid = _Last;
         for (; !(pMap? (*pMap)[*_Next] < (*pMap)[*--_Mid]: *_Next < *--_Mid);); 

         std::iter_swap(_Next, _Mid);
         std::reverse(_Next1, _Last);   
         return (true);
      }

      if (_Next == _First)
      {   
         std::reverse(_First, _Last);
         return (false);
      }
   }
}

vector<string> StlPermutation(const char* sz, bool bOrdered/*=true*/)
{
   vector<string> v;
   string s = sz;
   Position_Map mapPos;

   if (!bOrdered)
      for (unsigned int i=0; i<s.length(); i++)
         mapPos.insert(Position_Pair(s[i], i));   

   do   v.insert(v.end(), s);   
   while (_next_permutation(s.begin(), s.end(), bOrdered? NULL: &mapPos)); 

   return v;
}

In the caller StlPermutation(), if an input is considered as non-ordered when bOrdered is false, I set a position map that acts as a media for an artificial (simulated) comparison. Then, if this pMap is passed into _next_permutation(), I use comparison (*pMap)[*i]<(*pMap)[*j] for a non-ordered situation, instead of *i<*j. Now, just two condition changes there make it a dual function.

A Recursive Solution

Another way for non-ordered permutation is using recursion. Although not so efficient as iteration, it is easier to construct naturally mirroring the problem. I create a recursive function as follows, more concise than Steinhaus-Johnson-Trotter algorithm.

vector<string> RecPermutation(const char* sz)
{
   vector<string> v, v1;
   string s1;    char ch;
   int nLen = strlen(sz);      

   if (nLen==1)            // Base case: Add one-char string

      v.insert(v.end(), sz);      
   else                    // nLen > 1, need recursion

   {
      for (int i=0; i<nLen; i++)
      {
         ch = sz[i];       // Extract each char as the first

         s1 = sz;          // Copy the original string

         s1.erase(i, 1);   // Put the rest string into s1


         v1 = RecPermutation(s1.c_str()); // Recursive 


         for (int i=0; i < (int)v1.size(); i++)
         {   // Combine the extracted char with permuted strings 

            s1 = ch + v1[i];   
            v.insert(v.end(), s1);   
         }
      }
   }
      
   return v;
}

In this RecPermutation(), I strip each character aside, make a recursive call for the rest of the string, and once it returns, concatenates that character with permuted results. Obviously, this is more comprehensible than _next_permutation().

With Repeated Elements

Sometimes, we see a variation of non-ordered permutation where repeated elements are allowed. For instance, given �aab� or �aba�, the desired permutation pattern might be �aab�, �aba�, and �baa�, but from RecPermutation(), we still get six strings with each of the three appearing twice. Also, by a little modification of RecPermutation(), I achieved this method in the following function:

vector<string> RecPermutation(const char* sz, bool bRepeated)
{
   vector<string> v, v1;
   string s1;    char ch;
   int nLen = strlen(sz);      

   if (nLen==1)            // Base case: Add one-char string

      v.insert(v.end(), sz);      
   else                    // nLen > 1, need recursion

   {
      for (int i=0; i<nLen; i++)
      {
         ch = sz[i];       // Extract each char as the first


         // To exclude repeated element

         if (!bRepeated)
         {
            for (int j=0; j<i; j++)
               if (ch==sz[j]) break;

            if (j<i) continue;   // If i==j, Not a repeated one

         }

         s1 = sz;           // Copy the original string

         s1.erase(i, 1);    // Put the rest string into s1


         v1 = RecPermutation(s1.c_str(), bRepeated); // Recursive 


         for (int i=0; i < (int)v1.size(); i++)
         {
            s1 = ch + v1[i];   
            v.insert(v.end(), s1);   
         }
      }
   }

   return v;
}

As you see, I add the second parameter bAllowRepeated, and when this flag is false, I check the stripped character to skip repeated one if any. This simply enhances RecPermutation() as an alternative usage. Try to imagine altering an iteration function this way � really not easy!

Test and Comparison

Surely, you can search online for more permutation solutions. Among them, it�s worthy of mentioning this solution, created by Phillip Fuchs. There the iterative algorithm is pretty impressive and works efficiently for a non-ordered and non-repeated element list. I included his Example2 in my test program to examine an input "ijabcdefgh" as shown below:

Also, I made a comparison using the Permute.exe release build in my 2.2GHz P4 XP laptop, as shown in the following table:

Function            Parameter      Second(s)  #Permutations
-----------------------------------------------------------
_next_permutation   bOrdered=true        1         403,200       
_next_permutation   bOrdered=false       6       3,628,800
RecPermutation      bRepeated=true      45       3,628,800
RecPermutation      bRepeated=false     45       3,628,800
Philip's            example_02           5       3,628,800

As expected, the ordered _next_permutation() generates only part of permutations for the partially ascending "ijabcdefgh", while the non-ordered _next_permutation() generates all. The recursive RecPermutation() takes 45 seconds, not efficient as STL iteration (6 seconds), while Phillip�s example is a bit better than _next_permutation(). However, only the enhanced RecPermutation() excludes redundant permutations in a repeated element list, where the additional expense looks trivial.