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.
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.
Useful Links:
Below is the recursion tree using backtrack to find Permutations.
Program
Now let us see the Python Program to print all the permutations of a string.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def toStr(list): | |
| return ''.join(list) | |
| 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. | |
| """ | |
| if l==r: | |
| print(toStr(s)) | |
| 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) |
Time Complexity
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!)
