In this article we will discuss how to print all permutations of a given String using Python programming Language.
Before diving into the program, let us first see what is a Permutation.
A permutation is the rearrangement of the characters of a string. Let us take an example of the string “ABC”. Here the permutations of the respective string are ABC ACB BAC BCA CBA CAB.
Below is the recursion tree using backtrack to find Permutations.
Now let us see the Python Program to print all the permutations of a string.
|def permute(s, l, r):|
|Function to find permutations of a given sting|
|:arg s : string,|
|:arg l : left element of the string,|
|:arg r : right element of the string.|
|for i in range(l, r):|
|s[i], s[l] = s[l], s[i]|
|permute(s, l + 1, r)|
|s[i], s[l] = s[l], s[i] # backtrack|
|s = input('Enter a string:')|
|n = len(s)|
|a = list(s)|
|permute(a, 0, n)|
Now let us analyse the time complexity of the above backtracing algorithm used. Here the time taken to print a permutation is n as it has to travel down to the depth of n to print a permutation. No of permutations of a string of size n is n! Hence the total time to print all the permutations is O(n x n!)