Permutations
Permutations is the set of all different unique arrangements of the letters of the string. So for the string "ABC" there are 6 permutations - ABC, ACB, BAC, BCA, CAB, CBA. The permutations can also be taken on a smaller length. For example if we want to get permutations of ABC over only 2 places then the permutations are - AB, BA, AC, CA, BC, CB.
Now if the length of a string is n and the total number of places is r then the number of possible permutations is denoted as nPr and is equal to the value of the equation
n!/(n-r)!
So if there are 3 letters and 3 positions, there are 6 permutations.
That is ofcourse a very simple mathematical relation. In this post I am going to show you a simple C program that can generate all such permutations of a given string or word.
If you look at the problem carefully, you would understand that it is not possible to generate permutations with just a simple loop. A simpler way to do this is by using recursion. In recursion the task automatically gets broken down into smaller pieces. This is how it works.
Lets take a string ABCDE. Now to find all the permutations we need to do this.
A[permutations of BCDE] + B[permutations of ACDE] + C[permutations of ABDE] + D[permutations of ABCE] + E[permutations of ABCD]
Now we basically fix a letter in first position and find permutations of the rest of the places. Now lets take the first piece of the above equation.
A[permutation of BCDE]
Permutation of BCDE can again be calculated using the same logic as above. So basically we keep breaking down into smaller and smaller pieces till we are left with only 2 letters. When there are only 2 letters, the permutations are the 2 letters in forward and reverse order. For example AB and BA.
So now lets write a C program that will print all the permutations.
C Program to print the permutations
#include<stdio.h>
#include<conio.h>
#include<string.h>
void permute(char *str,int l,int pos,int r);
void swap(char &a,char &b);
void print_string(char *str,int r);
int main()
{
char str[10]="";
int l,r;
printf("Enter The String : ");
gets(str);
l=strlen(str);
printf("Enter The Number Of Places To permute on : ");
scanf("%d",&r);
printf("The Following Permuations are possible : nn");
permute(str,l,1,r);
getch();
return 0;
}
void permute(char *str,int l,int pos,int r)
{
//If lock position is on the next character
//than the limit
if(pos==r+1)
{
print_string(str,r); //print - these are the elements//
printf(" ");
return; //and return//
}
//true subscript of character in array is pos-1//
for(int i=pos-1;i<=l-1;i++)
{
//swap the first letter with all next letters
str[pos-1]=str[pos-1]+str[i]-(str[i]=str[pos-1]);
permute(str,l,pos+1,r);
//restore the swap{swap : a=a+b-(b=a)}
str[pos-1]=str[pos-1]+str[i]-(str[i]=str[pos-1]);
}
}
void print_string(char *str,int r)
{
for(int i=0;i<r;i++)
printf("%c",str[i]);
}
The function permute does the task of generating the permutations, by calling itself again and again (recursion).
For every given string, it keeps each letter in the first position once and calls itself on a subset without the first character.
Program Output
Now here is the output of the above program.
Enter The String : abcdef Enter The Number Of Places To permute on : 4 The Following Permuations are possible : abcd abce abcf abdc abde abdf abed abec abef abfd abfe abfc acbd acbe acbf acdb acde acdf aced aceb acef acfd acfe acfb adcb adce adcf adbc adbe adbf adeb adec adef adfb adfe adfc aecd aecb aecf aedc aedb aedf aebd aebc aebf aefd aefb aefc afcd afce afcb afdc afde afdb afed afec afeb afbd afbe afbc bacd bace bacf badc bade badf baed baec baef bafd bafe bafc bcad bcae bcaf bcda bcde bcdf bced bcea bcef bcfd bcfe bcfa bdca bdce bdcf bdac bdae bdaf bdea bdec bdef bdfa bdfe bdfc becd beca becf bedc beda bedf bead beac beaf befd befa befc bfcd bfce bfca bfdc bfde bfda bfed bfec bfea bfad bfae bfac cbad cbae cbaf cbda cbde cbdf cbed cbea cbef cbfd cbfe cbfa cabd cabe cabf cadb cade cadf caed caeb caef cafd cafe cafb cdab cdae cdaf cdba cdbe cdbf cdeb cdea cdef cdfb cdfe cdfa cead ceab ceaf ceda cedb cedf cebd ceba cebf cefd cefb cefa cfad cfae cfab cfda cfde cfdb cfed cfea cfeb cfbd cfbe cfba dbca dbce dbcf dbac dbae dbaf dbea dbec dbef dbfa dbfe dbfc dcba dcbe dcbf dcab dcae dcaf dcea dceb dcef dcfa dcfe dcfb dacb dace dacf dabc dabe dabf daeb daec daef dafb dafe dafc deca decb decf deac deab deaf deba debc debf defa defb defc dfca dfce dfcb dfac dfae dfab dfea dfec dfeb dfba dfbe dfbc ebcd ebca ebcf ebdc ebda ebdf ebad ebac ebaf ebfd ebfa ebfc ecbd ecba ecbf ecdb ecda ecdf ecad ecab ecaf ecfd ecfa ecfb edcb edca edcf edbc edba edbf edab edac edaf edfb edfa edfc eacd eacb eacf eadc eadb eadf eabd eabc eabf eafd eafb eafc efcd efca efcb efdc efda efdb efad efac efab efbd efba efbc fbcd fbce fbca fbdc fbde fbda fbed fbec fbea fbad fbae fbac fcbd fcbe fcba fcdb fcde fcda fced fceb fcea fcad fcae fcab fdcb fdce fdca fdbc fdbe fdba fdeb fdec fdea fdab fdae fdac fecd fecb feca fedc fedb feda febd febc feba fead feab feac facd face facb fadc fade fadb faed faec faeb fabd fabe fabc
