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.

Never miss Upcoming articles, free e-books, weekly updates on latest news from Android and Coding Community.

#### 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.

#### Program

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

0 0 vote
Article Rating

Subscribe
Notify of

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