Wednesday 25 November 2015

C program to print all the possible permutations of a string

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
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

Here's the code:

#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:
C-program-to-print-permutations-of-a-string

No comments:

Post a Comment