Permutations of a String
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 : 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]);
}
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% [?]
