Click here to Skip to main content
15,893,190 members
Articles / Programming Languages / C++

Implementing Permutation Variations

Rate me:
Please Sign up or sign in to vote.
4.75/5 (17 votes)
14 Jul 2004CPOL3 min read 81.6K   857   25  
Several enhanced permutation algorithms created in iterative or recursive solution.
// ============================================================================
// File:    Permutate.cpp - Main test of three character permutations
// Author:  Zuoliu Ding, May 2004
// Example: Permutation of characters in the string abc:
//          abc acb bac bca cab cba
// ============================================================================
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <time.h>
using namespace std;

// Three Permutation method prototypes
vector<string> StlPermutation(const char*, bool bOrdered=true);
vector<string> RecPermutation(const char*, bool bRepeated=true);
vector<string> example_02(const char* a);
//vector<string> StlPermutation(const char*);//=true);
//vector<string> RecPermutation(const char*);//=true);

// ============================================================================
// Function:    main
// Description: Test permutation functions.
// ============================================================================
void main()
{
   char         szSel[8];
   char          sz[32]; // "abcdefghijk"; // 

   while (true) 
   {
      cout << "Enter the first Letter to Select a Permutation Method:\n";
      cout << "-----------------------------------------------------------------------\n";
      cout << "S)TL   ";
      cout << "STL-N)o-Ordered   ";
      cout << "R)ecursion   ";
      cout << "Re-U)nrepeated   ";
//      cout << "I)teration,Enh  ";
      cout << "P)hil's   ";
      cout << "E)xit\n->";

      cin.getline(szSel, 8);
      *szSel = toupper(*szSel);
      if (*szSel =='E') return;

      if (*szSel !='R' && *szSel !='U' && *szSel !='S' && *szSel !='P' && *szSel !='N') 
      {
         cout << "Unrecognized Selection - Try again...\n\n";
         continue;
      }

      cout << "Enter a String for Permutation: ";
      cin.getline(sz, 32);
      cout << "Waiting ... ";

      vector<string> vStr;
      time_t t1, t2;
      time(&t1);

      vStr =(*szSel =='R')? RecPermutation(sz): 
            (*szSel =='U')? RecPermutation(sz, false): 
            (*szSel =='S')? StlPermutation(sz):
            (*szSel =='N')? StlPermutation(sz, false): example_02(sz);
//            (*szSel =='I')? EnhPermutationIteration(sz): StlPermutation(sz);

      time(&t2);

      cout << "\nTotal " << vStr.size() <<" permutations generated in result.txt.\n";

      if (strlen(sz)<5)
      {
         for (int i=0; i< (int)vStr.size(); i++) 
         {
            if (i) cout <<", ";
            cout << vStr[i];
         }
         cout << endl;
      }

      cout << "The time: " << long(t2-t1) <<" seconds.\n";

      if (strlen(sz)<11)
      {
         cout << "File saving ... ";

         ofstream fout("result.txt");   // Output file for all solutions
         fout <<((*szSel =='R')? "Recursive Permutation, Allow Repeated:": 
                 (*szSel =='U')? "Recursive Permutation, Not Repeated:": 
                 (*szSel =='S')? "STL, next_permutation, Ordered:":
                 (*szSel =='N')? "STL, next_permutation, Not Ordered:":
                                 "Iteration, Philip Paul's Example:") <<endl;

         for (int i=0; i< (int)vStr.size(); i++) 
         {
            if (i) fout <<", ";
            fout << vStr[i];
         }
         fout << endl;
         fout.close();
      }

      cout << endl << endl;
   }
}


By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions