Problem: Write the code for producing/printing permutations of the characters in a string. For example: If "abc" is the input string, output permutations should be "abc", "bac", "bca", "acb", "cab", "cba".
Solution: There are at least 2 approaches to solving this problem. Even though both approaches use recursion, there is a subtle difference between the two. The second approach uses more number of recursive calls than the first and my rough analysis has shown that run time of both approaches is almost same. The first approach would be preferable given that the there are only n recursive calls compared to n! recursive calls of the second approach. Approach 1:
Pseudo Code:
Approach 2:
The idea here is to put each character in the string in the 1st position and combine it with the permutation of the characters in the rest of the string. As you can see this is also a recursive definition. Pseudo Code:
Solution: There are at least 2 approaches to solving this problem. Even though both approaches use recursion, there is a subtle difference between the two. The second approach uses more number of recursive calls than the first and my rough analysis has shown that run time of both approaches is almost same. The first approach would be preferable given that the there are only n recursive calls compared to n! recursive calls of the second approach. Approach 1:
Pseudo Code:
1. Set index = 0 to point to the 1st character in the input string
2. If index = n-1 return last character (n is length of input string)
3. Get Permutations of string starting at index + 1
4. For each permutation in the list from step 3
a. Insert input[index] character in all possible positions of each
permutation.
Example:
input = "abc"
get permutations for "bc": "bc" and "cb"
insert "a" in all positions of both "bc" and "cb":
"a" * "bc": "abc", "bac", "bca"
"a" * "cb": "acb", "cab", "cba"
Code (C#): List<string> Permute(string, str, int startIndex)
{
if(startIndex == str.Length -1 )
return new string[]{str.Substring(startIndex)};
List<string> permutations = Permute(str, ++startIndex);
List<string> newPermutations = new List<string>();
foreach(string permutation in permutations)
{
for(int i=0; i<permutation.Length; i++)
{
newPermutations.Add(permutation.Insert(i, str[startIndex]));
}
}
return newPermutations;
}
Analysis: Number of recursive calls is equal to N (length of the input string). if L is the level of each recursive call, the run time for each recursive call is L!. So at the top most call, since L = N, it is N!. Total: N! + N-1! + N-2! ... + 1 Approach 2:
The idea here is to put each character in the string in the 1st position and combine it with the permutation of the characters in the rest of the string. As you can see this is also a recursive definition. Pseudo Code:
For i=0 to N 1. Swap letters 0 and i. 2. Permute letters 1 to N-1, printing or saving the entire string each time.Code (C):
Permute(char* inputStart, char* current)
{
char *swap;
char temp;
if(*(current + 1) = '\0')
printf("%s\n", inputStart);
else
{
for(swap = current; *swap != '\0'; ++swap)
{
temp = *swap;
*swap = *current;
*current = temp;
Permute(inputStart, current + 1);
//revert the letters
*current = *swap;
*swap = temp;
}
}
}
Run time: This solution makes at least N! + N-1! + N-2!+ ... + 1 recursive calls doing 1 unit of work in each call. Compare this to the less number of recursive calls from the approach one, but approach one does increasing more work going back up from each recursive call.
