Given a string, write a Python program to find out all possible permutations of a string. Let’s discuss a few methods to solve the problem.
Method #1: Using Naive Method
Python3
# Python code to demonstrate# to find all permutation of# a given string# Initialising stringini_str = "abc"# Printing initial stringprint("Initial string", ini_str)# Finding all permutationresult = []def permute(data, i, length): if i == length: result.append(''.join(data) ) else: for j in range(i, length): # swap data[i], data[j] = data[j], data[i] permute(data, i + 1, length) data[i], data[j] = data[j], data[i] permute(list(ini_str), 0, len(ini_str))# Printing resultprint("Resultant permutations", str(result)) |
Output:
Initial string abc Resultant permutations ['abc', 'acb', 'bac', 'bca', 'cba', 'cab']
Method #2: Using itertools
Python3
# Python code to demonstrate# to find all permutation of# a given stringfrom itertools import permutations# Initialising stringini_str = "abc"# Printing initial stringprint("Initial string", ini_str)# Finding all permutationpermutation = [''.join(p) for p in permutations(ini_str)]# Printing resultprint("Resultant List", str(permutation)) |
Output:
Initial string abc Resultant List ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Using recursion:
Approach:
If the length of the string is 1, return a list containing the string
Otherwise, for each character in the string:
a. Fix the current character and recursively find all permutations of the remaining characters
b. Add the current character to the beginning of each permutation
c. Append the permutations to a list and return the list
Python3
def find_permutations(s): if len(s) == 1: return [s] else: perms = [] for i, c in enumerate(s): for perm in find_permutations(s[:i] + s[i+1:]): perms.append(c + perm) return permss = 'abc'print(find_permutations(s)) |
Output
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Time complexity: O(n!)
Auxiliary Space: O(n!)
