This post has already been read 7921 times!

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

These permute2 values themselves can be broken down to smaller subproblems.
CodeCogsEqn (1)

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 subproblem of permuting a smaller string.

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

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:
CodeCogsEqn

PHP 

// function to generate and print all N! permutations of $str. (N = strlen($str)).
function permute($str, $i, $n) {
	
   if ($i == $n)
   {
       print $str."\n";
   }
   else {
        for ($j = $i; $j < $n; $j++) 
        {
          swap($str,$i,$j);
          
          permute($str, $i+1, $n);
          
          swap($str,$i,$j); // backtrack.
       }
   }
}

// function to swap the char at pos $i and $j of $str.
function swap(&$str,$i,$j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}   

$str = "ABC";
permute($str,0,strlen($str)); // call the function.

str = ABC j = 0 i = 0 => switch : A and A 
str = ABC j = 1 i = 1 => switch : B and B 
str = ABC j = 2 i = 2 => switch : C and C 
================ 
=> solution : ABC 
================ 

str = ABC j = 2 i = 1 => switch : B and C 
str = ACB j = 2 i = 2 => switch : B and B 
================ 
=> solution : ACB 
================ 

str = ABC j = 1 i = 0 => switch : A and B 
str = BAC j = 1 i = 1 => switch : A and A 
str = BAC j = 2 i = 2 => switch : C and C 
================ 
=> solution : BAC 
================ 

str = BAC j = 2 i = 1 => switch : A and C 
str = BCA j = 2 i = 2 => switch : A and A 
================ 
=> solution : BCA 
================ 

str = BAC j = 2 i = 0 => switch : B and C 
str = CAB j = 1 i = 1 => switch : A and A 
str = CAB j = 2 i = 2 => switch : B and B 
================ 
=> solution : CAB 
================ 

str = CAB j = 2 i = 1 => switch : A and B 
str = CBA j = 2 i = 2 => switch : A and A 
================ 
=> solution : CBA 
================ 

http://www.divye.in/2011/06/printing-all-permutations-of-string.html

Comments are closed.

Post Navigation