/*****************************************************************
 * Suppose we have a list containing the letters
 *
 *    a, b, c, d
 *
 * Now, here's are the first 10 permutations ...
 *
 *    a b c d         0
 *    a b d c         1
 *    a c d b         2
 *    a c b d         3
 *    a d b c         4
 *    a d c b         5
 *    b c d a         6
 *    b c a d         7
 *    b d a c         8
 *    b d c a         9
 *    ...
 * 
 * Notice that each permutation is produced by reversing
 * a part of the previous permutation, for example:
 *
 *    a b c d       0
 *    a b d c       1
 *
 * Here we're reversing the sub string "c d" to get from
 * permutation 0 to permutation 1.  Similarly ...
 *
 *    a c b d         3
 *    a d b c         4
 *
 *    a d c b         5
 *    b c d a         6
 *
 * Here, to get from 3 to 4 we're reversing the string "c b d", to
 * get from 5 to 6 we're reversing "a d c b".  Each time we're
 * reversing the last n characters of the string, the pattern
 * looks like this ...
 *
 *    Last 'n' characters      Permutation
 *    -------------------      -----------
 *           N/A                    0
 *           2                      1
 *           3                      2
 *           2                      3
 *           3                      4
 *           2                      5
 *           4                      6
 *           2                      7
 *           3                      8
 *           2                      9
 *          ...
 *
 * Now, for each permutation number { 1, ..., 23 } we find the
 * largest factorial value that divides evenly into the
 * permutation number.  The factorial values less than 23 are:
 *
 *    1! -> 1
 *    2! -> 2
 *    3! -> 6
 *
 * permutation number   biggest divisor   reverse last n chars
 * ------------------   ---------------   --------------------
 *        4                   2!                  3
 *        5                   1!                  2
 *        6                   3!                  4
 *****************************************************************/

// ---------------------------------------------------------------
// C/C++ Headers
// ---------------------------------------------------------------

#include <vector>
#include <string>
#include <iostream>
#include <sstream>

using std::vector;
using std::string;
using std::cout;
using std::endl;
using std::ostringstream;

// ---------------------------------------------------------------
// Declaration: template class Permute
// ---------------------------------------------------------------

template <typename T>
class Permute
{
   public:

      Permute(vector<T> items);
      Permute(string s);
      Permute(T *items, int nItems);

      void  reset();
      const vector<T> *getNext();

      static string toString(
         const  vector<T> *items,
         string separator = " "
      );

   private:

      void init(vector<T> items);

      vector<T>   mOriginal;
      vector<T>   mCurrent;
      int         mTotalPermutations;
      int         mIteration;
      vector<int> mFactorials;
};

// --------------------------------------------
// Construct from vector of items of type 'T'
// --------------------------------------------

template <typename T>
Permute<T>::Permute(vector<T> items)
{
   init(items);
}

// --------------------------------------------
// Construct from a string
// --------------------------------------------

template <>
Permute<char>::Permute(string s)
{
   vector<char> v;

   for(int i = 0, n = s.length(); i < n; i ++)
      v.push_back(s[i]);

   init(v);
}

// --------------------------------------------
// Construct from an array of type 'T'
// --------------------------------------------

template <typename T>
Permute<T>::Permute(T *items, int nItems)
{
   vector<T> v;

   for(int i = 0; i < nItems; i ++)
      v.push_back(items[i]);

   init(v);
}

// --------------------------------------------
// Restart the permutations from the beginning
// --------------------------------------------

template <typename T>
void Permute<T>::reset()
{
   mIteration = 0;
   mCurrent   = mOriginal;
}

// --------------------------------------------
// Return a pointer to a vector of 'T' items
// or NULL if we've already been through
// all of the permutations
// --------------------------------------------

template <typename T>
const vector<T> *Permute<T>::getNext()
{
   if(mIteration == mTotalPermutations)
      return(0);

   if(mIteration > 0)
   {
      int i = 0;

      for(i = mCurrent.size() - 1; i > 1; i --)
         if(mIteration % mFactorials[i] == 0)
            break;

      for(int j = 0, k = i; j < k; j ++, k --)
      {
         T tmp       = mCurrent[j];
         mCurrent[j] = mCurrent[k];
         mCurrent[k] = tmp;
      }
   }

   const vector<T> *ptr = &mCurrent;
   mIteration++;

   return(ptr);
}

// --------------------------------------------
// static utility method - create a string
// from a vector of type 'T' with each element
// separated by 'separator'
// --------------------------------------------

template <typename T>
string Permute<T>::toString(const vector<T> *items, string separator)
{
   ostringstream out;

   for(int n = items->size(), i = 0; i < n; i ++)
   {
      if(i > 0)
         out << separator;

      out << items->at(i);
   }

   return(out.str());
}

template <typename T>
void Permute<T>::init(vector<T> items)
{
   int length = items.size();

   mOriginal          = items;
   mCurrent           = items;
   mTotalPermutations = length;
   mIteration         = 0;

   for(int i = 0; i < length; i ++)
   {
      if(i < 2)
      {
         mFactorials.push_back(i);
      }
      else
      {
         mTotalPermutations *= i;
         mFactorials.push_back(i * mFactorials[i - 1]);
      }
   }
}

template <typename T>
void show(Permute<T> &p)
{
   p.reset();

   while(true)
   {
      const vector<T> *current = p.getNext();

      if(!current)
         break;

      cout << Permute<T>::toString(current) << endl;
   }
}

int main()
{
   // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   // Permute a string
   // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

   Permute<char> pLetters("abcd");

   show(pLetters);

   // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   // Permute an array of strings
   // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

   string strings[] = { "red", "green", "blue", "yellow" };
   int n            = sizeof(strings) / sizeof(strings[0]);

   Permute<string> pStrings(strings, n);

   show(pStrings);

   // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   // Permute a vector of integers
   // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

   vector<int> integers;

   for(int i = 0; i < 4; i ++)
      integers.push_back(i + 1);

   Permute<int> pNumbers(integers);
   show(pNumbers);

   return(0);
}