Python Program to Find All Permutations of a String

You can find all permutations of a string in Python using itertools.permutations(string) or by writing a recursive function that swaps characters to generate all possible orders.

Examples

Inputabc

Output['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Inputa

Output['a']

Input

Output['']

How to Think About It

To find all permutations of a string, think of arranging each character in every possible order. You can do this by picking one character at a time and recursively finding permutations of the remaining characters until none are left.

Algorithm

1

Get the input string.

2

If the string is empty, return a list with an empty string.

3

For each character in the string, fix that character and find permutations of the remaining substring.

4

Combine the fixed character with each permutation of the remaining substring.

5

Collect all these combined strings and return them as the result.

Code

python

from itertools import permutations

def all_permutations(s):
    return [''.join(p) for p in permutations(s)]

print(all_permutations('abc'))

Output

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Dry Run

Let's trace the input 'abc' through the itertools permutations code.

1

Input string

s = 'abc'

2

Generate permutations

permutations('abc') generates tuples: ('a','b','c'), ('a','c','b'), ('b','a','c'), ('b','c','a'), ('c','a','b'), ('c','b','a')

3

Join tuples to strings

Each tuple is joined to form strings: 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'

4

Return list

Return list of all these strings.

Permutation Tuple	Joined String
('a','b','c')	abc
('a','c','b')	acb
('b','a','c')	bac
('b','c','a')	bca
('c','a','b')	cab
('c','b','a')	cba

Why This Works

Step 1: Using itertools.permutations

The permutations function generates all possible orderings of the input characters as tuples.

Step 2: Joining tuples to strings

Each tuple of characters is joined back into a string to represent one permutation.

Step 3: Collecting all permutations

All these strings are collected into a list and returned as the final result.

Alternative Approaches

Recursive function

python

def permute(s):
    if len(s) == 0:
        return ['']
    result = []
    for i, c in enumerate(s):
        for perm in permute(s[:i] + s[i+1:]):
            result.append(c + perm)
    return result

print(permute('abc'))

This method uses recursion to build permutations by fixing one character and permuting the rest; it is easy to understand but less efficient than itertools.

Using backtracking

python

def backtrack(chars, path, used, res):
    if len(path) == len(chars):
        res.append(''.join(path))
        return
    for i in range(len(chars)):
        if used[i]:
            continue
        used[i] = True
        path.append(chars[i])
        backtrack(chars, path, used, res)
        path.pop()
        used[i] = False

chars = list('abc')
result = []
backtrack(chars, [], [False]*len(chars), result)
print(result)

Backtracking builds permutations step-by-step and is useful for learning recursion and state management but requires more code.

Complexity: O(n!) time, O(n!) space

Time Complexity

Generating all permutations requires factorial time because there are n! ways to arrange n characters.

Space Complexity

Storing all permutations requires factorial space since each permutation is stored as a string.

Which Approach is Fastest?

Using itertools.permutations is fastest and most memory-efficient due to optimized C implementation; recursive and backtracking methods are slower and use more memory.

Approach	Time	Space	Best For
itertools.permutations	O(n!)	O(n!)	Quick, efficient, built-in
Recursive function	O(n!)	O(n!)	Learning recursion, clarity
Backtracking	O(n!)	O(n!)	Understanding recursion and state