Question:
Print all permutations of a given string.
Example:
Input string: ABC.
Output: ABC ACB BAC BCA CBA CAB
No of String=6
Solution:
Approach:
Begin
if left = right, then
display str
else
for i := left to right, do
swap str[left] and str[i]
stringPermutation(str, left+1, right)
swap str[left] and str[i] //for backtrack
done
End
C program:
#include <stdio.h>
#include <string.h>
int count=0;
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
/* Function to print permutations of string*/
void permute(char *a, int l, int r)
{
int i;
if (l == r){
printf("%d) %s\n",count+1,a);
count++;
}
else
{
for (i = l; i <= r; i++) {
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i)); //backtrack
}
}
}
int main()
{
char str[100];
printf("Enter the String ");
scanf("%s",str);
int n = strlen(str);
permute(str, 0, n-1);
printf("Total number of Strings possible from String:%s =%d",str,count);
return 0;
}
Output:
Enter the String qwer
1) qwer
2) qwre
3) qewr
4) qerw
5) qrew
6) qrwe
7) wqer
8) wqre
9) weqr
10) werq
11) wreq
12) wrqe
13) ewqr
14) ewrq
15) eqwr
16) eqrw
17) erqw
18) erwq
19) rweq
20) rwqe
21) rewq
22) reqw
23) rqew
24) rqwe
Total number of Strings possible from String:qwer = 24
0 comments:
Post a Comment