Monday, May 27, 2024
Home Algorithms Print all permutations of a string using Python

Print all permutations of a string using Python

Print all permutations of a string using Python

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.

Useful Links:


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



Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.