Permutation algorithm

**WarBaboon** · 03-17-2003

Here's my problem. Say you have a certain set of data, of which type is unimportant. For example's sake, let's use an array of 4 characters.

Code:

char array[4] = "abcd";

Now I want to create a program that will output every single permutation possible of these characters :

abcd
abdc
acbd
acdb
adbc
and so on...

Are there any good resources/code/tutorials on the matter ? Does anybody have hints on how to make that ? Thanks.

**quzah** · 03-17-2003

char array[4] = "abcd";

You forgot room for the null. You either need to:

a) Implicitly assign each character to the array, one at a time.
b) Include room for the null so you can do your string assignment.

This issue (the main issue, not your incorrect array usage) comes up from time to time. You should search the board, there's likely a ton of posts for the same topic.

Quzah.

**PJYelton** · 03-18-2003

One such solution would be to use a recursive function like so:

Code:

void recursiveFunc(int num, string &fullString, string partString, int maxNum)
{
        int partStringSize=partString.size();
        partString+=" ";
        for (int x=0; x<fullString.size(); ++x)
        {
            partString[partStringSize]=fullString[x];
            if (num==maxNum)
                cout<<partString;
            else
                recursiveFunc(num+1, fullString, partString, maxNum);
         }
}

int main()
{
    string myString="abcd";
    string partString="";
    recursiveFunc(1, myString, partString, myString.size());
    return 0;
}

This works, BUT it will print repeats like "aaaa". If you don't want these then I guess you would need to do a check in the recursive function. I'm sure there are possibly more elegant solutions that aren't as brute forceish, let me know if you find one!

**Stoned_Coder** · 03-18-2003

just use next_permutation. Dead easy. M$hit sample...

Code:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using namespace std ;

int main()
{
    const int VECTOR_SIZE = 3 ;

    // Define a template class vector of strings
    typedef vector<string> StrVector ;

    //Define an iterator for template class vector of strings
    typedef StrVector::iterator StrVectorIt ;

    //Define an ostream iterator for strings
    typedef ostream_iterator<string> StrOstreamIt;

    StrVector Pattern(VECTOR_SIZE) ;

    StrVectorIt start, end, it ;

    StrOstreamIt outIt(cout, " ") ;

    start = Pattern.begin() ;   // location of first
                                // element of Pattern

    end = Pattern.end() ;       // one past the location last
                                // element of Pattern

    //Initialize vector Pattern
    Pattern[0] = "A" ;
    Pattern[1] = "B" ;
    Pattern[2] = "C" ;

    // print content of Pattern
    cout << "Before calling next_permutation:\n" << "Pattern: " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << "\n\n" ;

    // Generate all possible permutations

    cout << "After calling next_permutation:" << endl ;
    while ( next_permutation(start, end) )
    {
        copy(start, end, outIt) ;
        cout << endl ;
    }
}

**hk_mp5kpdw** · 03-18-2003

If you use the method described by Stoned_Coder, your initial pattern that is stored in the array must be in sorted (ascending) order or it will not go through all of the necessary permutations. If you were, for whatever reason, to use the prev_permutation function instead, the starting pattern would need to be stored in descending order (i.e. "DCBA") for it to work properly.

**CtrlAltKick** · 03-18-2003

i found this code on the net a while ago. it was originally in c++ but i changed it to c because i had never messed with c++ before. i also added a sort function and a main driver so i could play with it a bit. i finally had to sit down with paper and pencil to understand how it worked (probably because im slow). anyway, hope it helps.

Code:

#include <stdio.h>
#include <string.h>

typedef enum { FALSE, TRUE } BOOL;

void swap(char *a, char *b)
{
   char t = *a;

   *a = *b; *b = t;
}

void rev(char *begin, char *end)
{
   if(*end == '\0') end--;
   while(begin < end)
   { swap(begin, end); begin++; end--; }
}

BOOL NextPerm(char *first, char *last)
{
   char *a, *b, *c;

   if(first == last) return FALSE;

   a = first; a++;

   if(a == last) return FALSE;

   a = last; a--;

   for(;/*ever*/;)
   {
      b = a--;
      if(*a < *b)
      {
         c = last;

         while(!(*a < *--c));

         swap(a, c); rev(b, last);
         return TRUE;
      }
      if(a == first)
      { rev(first, last); return FALSE; }
   }
}

void InsertionSort(char *a, int l, int r)
{
   char v;
   int  i, j;

   for(i = l + 1; i <= r; i++)
   {
      j = i - 1; v = a[i];
      while(j >= l && (v < a[j]))
      { a[j+1] = a[j]; j--; }
      a[j+1] = v;
   }
}

int main(int argc, char *argv[])
{
   char *begin, *end;
   int  col = 0;

   if(argc < 2)
   { printf("usage: perm <arg>\n"); return 0; }

   InsertionSort(argv[1], 0, strlen(argv[1]) - 1);

   while(NextPerm(argv[1], argv[1] + strlen(argv[1])))
   {
      if(col++ % 3 == 0) printf("\n");
      printf("%-15s", argv[1]);
   }
   printf("%-15s\n", argv[1]);

   return 0;
}

btw, i realize other people have already offered solutions, but i thought you might be interested.

**WarBaboon** · 03-18-2003

Thanks for the help/code, everyone. And yes, I shall use the Search from now on, Quzah.

Thread: Permutation algorithm

Thread Tools

Search Thread

Display

Permutation algorithm

Similar Threads

Permutation algorithm??

Binary Search Trees Part III

Request for comments

permutation algorithm