Programming: C program to print all permutations of a given string

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.

These permute2 values themselves can be broken down to smaller subproblems.

Here, it is obvious that permute1(any char) = char itself. This is the base case of this recursion. Unrolling the recursion for the 3 required values yields:

permute2(“BC”) = { “BC”, “CB” }
permute2(“AC”) = { “AC”, “CA”}
permute2(“AB”) = {“AB”, “BA”}

So the resultant sets of strings are:
permute3(“ABC”) = {“ABC”, “ACB”} U {“BAC”, “BCA”} U {“CAB”, “CBA”}

which is the set of all permutations of the string “ABC”. It is obvious to see that we are in fact just choosing the starting prefix of the permutation and then requesting the permute function to run on a smaller sub-problem of permuting a smaller string.

To generalize, we can state that we can get all the permutations of a string using the general recurrence:

C
# include 
 
/* 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!)

Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.

The diagram shows recursive execution of permute()

For i = 0 and j = 0
A is fixed at first place using below line
swap((a+i), (a+j)) /*A is swapped with A*/
Then all the permutations of BC (sub-string after A) are printed
permute(a, i+1, n);  /*Call permute for BC  with i = 1  */
Finally swap the characters back
swap((a+i), (a+j)) /*A is swapped with A*/
For i = 0 and j = 1
B is fixed at first place using below line
swap((a+i), (a+j)) /*A is swapped with B*/
Then all the permutations of BC (sub-string after A) are printed
permute(a, i+1, n);  /*Call permute for AC  with i = 1 */
Finally, swap the characters back
swap((a+i), (a+j)) /*B is swapped with A*/
For i = 0 and j = 2
C is fixed at first place using below line
swap((a+i), (a+j)) /*A is swapped with C*/
Then all the permutations of BC (sub-string after A) are printed
permute(a, i+1, n);  /*Call permute for BA with i = 1 */
Finally, swap the characters back
swap((a+i), (a+j)) /*C is swapped with A*/
For i = 1, second character is swapped one by one with the other characters (after second character). Same way is continued for i = 2, 3..

To understand how this works, just look at the string “ABC”.

Let us assume that we have a magic function permute2 that generates all possible permutations of a given string of length 2.

Then, the permutations problem for the string “ABC” can then be broken down as:

Hope it will be useful to you.. Source: http://www.eandbsoftware.org/