Given a string,the task is to print all the permutations of the string.
A permutation is a rearrangement of the elements of an ordered list S.A string of length N has N! permutations.
Example-
Let the string be S=”abc”.
Length of the string=3
Number of permutations=3!=6
Permutations-
abc
acb
bac
bca
cab
cba
Algorithm-
Basic idea-
All permutations of a string X is the same thing as all permutations of each possible character in X, combined with all permutations of the string X without that letter in it.
All permutations of “abcd” are-
“a” concatenated with all permutations of “bcd”.
“b” concatenated with all permutations of “acd”.
“c” concatenated with all permutations of “bad”.
“d” concatenated with all permutations of “bca”.
Recursive solution-
The first character is kept constant and permutations are generated with the rest.Then,the first two characters are kept constant and permutations are generated with the rest until we are out of characters.
This algorithm is performed on the input string itself.Thus,no additional memeory is required.The “backtracking” undoes the changes to the string, leaving it in its original state.
Code-
[cpp]
char a[1000];//string
//to swap characters at position i and j
void swap (int i, int j)
{
char temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//i is the starting index
//n is the ending index
//initially,permute(0,n-1) is called
void permute(int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
swap(i,j);
//increasing the number of fixed characters
permute(i+1, n);
swap(i,j); //backtrack
}
}
}
[/cpp]
Note-
It has a time complexity of O(N*N!) and is an example of Backtracking.
