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