Find all permutations of a string in Python

In this post, we will see how to list out all permutations of a string in Python.

For example, the string ABC has 6 permutations, i.e., ABC, ACB, BAC, BCA, CBA, CAB.

Practice this problem

In Python, we can use the built-in module itertools to get permutations of elements in the list using the permutations() function.

import itertools

if __name__ == '__main__':

s = 'ABC'

nums = list(s)

permutations = list(itertools.permutations(nums))

# Output: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

print([''.join(permutation) for permutation in permutations])

However, we can also write your utility function to generate all permutations of a string. We can do this either recursively or iteratively.

1. Recursive Implementation

The idea is to convert the given string to a character array, and in-place generate all its permutations using backtracking.

We can do this by swapping each of the remaining characters in the string with its first character and generating all the permutations of the remaining characters using a recursive call. This is illustrated in the recursion tree shown below.

Permutations of a String

# Function to swap two characters in a character array

def swap(ch, i, j):

temp = ch[i]

ch[i] = ch[j]

ch[j] = temp

# Recursive function to generate all permutations of a string

def permutations(ch, curr_index=0):

if curr_index == len(ch) - 1:

print(''.join(ch))

for i in range(curr_index, len(ch)):

swap(ch, curr_index, i)

permutations(ch, curr_index + 1)

swap(ch, curr_index, i)

if __name__ == '__main__':

s = 'ABC'

permutations(list(s))

Download Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

Here’s another implementation in Python which doesn’t convert the string to a character array.

# Recursive function to generate all permutations of a string

def permutations(remaining, candidate=''):

if len(remaining) == 0:

print(candidate)

for i in range(len(remaining)):

newCandidate = candidate + remaining[i]

newRemaining = remaining[0:i] + remaining[i+1:]

permutations(newRemaining, newCandidate)

if __name__ == '__main__':

s = 'ABC'

permutations(s)

Download Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

2. Iterative Implementation

The idea is to store the partially generated permutations and then use those partial permutations to generate the final permutations in further iterations. Here’s how the code would look like:

# Iterative function to generate all permutations of a string in Python

def permutations(s):

# base case

if not s:

return []

# create a list to store (partial) permutations

partial = []

# initialize the list with the first character of the string

partial.append(s[0])

# do for every character of the specified string

for i in range(1, len(s)):

# consider previously constructed partial permutation one by one

# iterate backward

for j in reversed(range(len(partial))):

# remove the current partial permutation from the list

curr = partial.pop(j)

# Insert the next character of the specified string into all

# possible positions of current partial permutation.

# Then insert each of these newly constructed strings into the list

for k in range(len(curr) + 1):

partial.append(curr[:k] + s[i] + curr[k:])

print(partial, end='')

if __name__ == '__main__':

s = 'ABC'

permutations(s)

Download Run Code

Output:

[‘CAB’, ‘ACB’, ‘ABC’, ‘CBA’, ‘BCA’, ‘BAC’]

The time complexity of the above solutions is O(n.n!) since there are n! permutations for a string of length n, and each permutation takes O(n) time.

Find all permutations of a string in Python

1. Recursive Implementation

2. Iterative Implementation

Share this: