C Program to print permutations of a string

An article by Silver Moon    No Comments

If the length of a string is n and the total number of places is r then the number of possible permutations is nPr or n!/(n-r)! . That is ofcourse a very simple mathematical relation. Only loops would not be a good idea to generate the permutations when n , r are both unbounded and variable. Recursion helps.

The following program does the task :

#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 : \n\n");
  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]);
}

An Output like this comes :

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

Popularity: 2% [?]