# Permutation algorithm

• 03-17-2003
WarBaboon
Permutation algorithm
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
and so on...

Are there any good resources/code/tutorials on the matter ? Does anybody have hints on how to make that ? Thanks.
• 03-17-2003
quzah
Quote:

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.
• 03-18-2003
PJYelton
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! :)
• 03-18-2003
Stoned_Coder
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 ;
}
}

• 03-18-2003
hk_mp5kpdw
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.
• 03-18-2003
CtrlAltKick
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.
• 03-18-2003
WarBaboon
Thanks for the help/code, everyone. And yes, I shall use the Search from now on, Quzah. :)