C Program to print permutations of a string

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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
(Visited 11 times, 1 visits today)

Comments

comments

Leave a Reply