This post has already been read 8348 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.

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

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:

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