There are many ways in which we can do this, I have written the code in C and used backtracking to solve the problem and I think it is very easy to understand as well as to implement.
For eg: String: "ABC"
we can find all the possible permutations :
First Call:
1st iteration
fix A, permutate remaining string "BC"
Recursive call: fix B, permutate C
when we reach the last character print the string which is: ABC
recursive call: fix C permutate B resulting string is: ACB
First Call:
2nd iteration
fix B, permutate remaining string "AC"
Recursive call: fix A, permutate C
when we reach the last character print the string which is: BAC
recursive call: fix C permutate A resulting string is: BCA
Here's the code:
For eg: String: "ABC"
we can find all the possible permutations :
First Call:
1st iteration
fix A, permutate remaining string "BC"
Recursive call: fix B, permutate C
when we reach the last character print the string which is: ABC
recursive call: fix C permutate B resulting string is: ACB
First Call:
2nd iteration
fix B, permutate remaining string "AC"
Recursive call: fix A, permutate C
when we reach the last character print the string which is: BAC
recursive call: fix C permutate A resulting string is: BCA
First Call:
3rd iteration
fix C, permutate remaining string "AB"
Recursive call: fix B, permutate A
when we reach the last character print the string which is: CBA
recursive call: fix A permutate B resulting string is: CAB
3rd iteration
fix C, permutate remaining string "AB"
Recursive call: fix B, permutate A
when we reach the last character print the string which is: CBA
recursive call: fix A permutate B resulting string is: CAB
#include<stdio.h> #include<string.h> void swap(char *s, int x,int y){ int swap; swap=s[x]; s[x]=s[y]; s[y]=swap; } void permutate(char *s,int st,int en){ int i; if(st==en) printf("%s\n",s); else for(i=st;i<=en;i++){ swap(s,st,i); permutate(s,st+1,en); swap(s,st,i); } } int main(){ char str[1000]; int startIndex,endIndex; printf("Enter the String: "); scanf("%s",str); startIndex=0; endIndex=strlen(str)-1; permutate(str,startIndex,endIndex); return 0; }Sample Output:
No comments:
Post a Comment