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.
Sreekumar (KJ) has been a hobby programmer from school days. Codemarvels is his personal blog from the year 2010, where he writes about technology, philosophy, society and a bit about physics.
He now runs a conversational AI company – DheeYantra – focusing his efforts to help businesses improve operational efficiency using digital employees powered by AI.