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:

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) = '')
      printf("%s\n", inputStart);
   else
   {
      for(swap = current; *swap != ''; ++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.

Write a C program to print all permutations of a given string

August 2, 2009

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.
Source: Mathword(http://mathworld.wolfram.com/Permutation.html)

Below are the permutations of string ABC.
ABC, ACB, BAC, BCA, CAB, CBA

Here is a solution using backtracking.

NewPermutation

# include <stdio.h>
/* 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
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
}
/* Driver program to test above functions */
int main()
{
   char a[] = "ABC"
   permute(a, 0, 2);
   getchar();
   return 0;
}

Output:

ABC
ACB
BAC
BCA
CBA
CAB


Algorithm Paradigm:
Backtracking
Time Complexity: O(n*n!)

The algorithm basically works on this logic:

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.

That is to say, 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"

This algorithm in particular instead of performing recursion on substrings, performs the recursion in place on the input string, using up no additional memory for allocating substrings. The "backtracking" undoes the changes to the string, leaving it in its original state.

END