algorithm for python itertools.permutations

Python

itertools

permutations

algorithms

programming

algorithm for python itertools.permutations

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

itertools.permutations generates all possible orderings of elements from an iterable. It returns tuples of a specified length (defaulting to the full length of the input). The function uses a lazy iterator, producing permutations one at a time without generating all of them in memory. Understanding the underlying algorithm helps when you need custom permutation logic or want to optimize for specific use cases.

Basic Usage

python

1from itertools import permutations
2
3# All permutations of a list
4list(permutations([1, 2, 3]))
5# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
6
7# Permutations of length r
8list(permutations([1, 2, 3], r=2))
9# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
10
11# String permutations
12list(permutations('ABC', 2))
13# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

The signature is itertools.permutations(iterable, r=None):

iterable: Any iterable (list, tuple, string, range, etc.)
r: Length of each permutation tuple. Defaults to len(iterable) for full-length permutations

How Many Permutations?

The number of r-length permutations from n elements is P(n, r) = n! / (n-r)!:

python

1from math import perm  # Python 3.8+
2
3# Full permutations of 4 elements: 4! = 24
4print(perm(4))      # 24
5
6# 2-length permutations from 4 elements: 4! / 2! = 12
7print(perm(4, 2))   # 12
8
9# 10-length permutations of 10 elements: 10! = 3,628,800
10print(perm(10))     # 3628800

The Algorithm Behind itertools.permutations

CPython's itertools.permutations uses a variant of the Steinhaus-Johnson-Trotter algorithm adapted for index-based generation. Here is a simplified Python equivalent:

python

1def permutations_equivalent(iterable, r=None):
2    pool = tuple(iterable)
3    n = len(pool)
4    r = n if r is None else r
5    if r > n:
6        return
7
8    indices = list(range(n))
9    cycles = list(range(n, n - r, -1))
10
11    yield tuple(pool[i] for i in indices[:r])
12
13    while n:
14        for i in reversed(range(r)):
15            cycles[i] -= 1
16            if cycles[i] == 0:
17                indices[i:] = indices[i+1:] + indices[i:i+1]
18                cycles[i] = n - i
19            else:
20                j = cycles[i]
21                indices[i], indices[-j] = indices[-j], indices[i]
22                yield tuple(pool[i] for i in indices[:r])
23                break
24        else:
25            return

The key idea: maintain an array of indices and a cycles counter. Each step swaps elements and decrements cycle counters. When a cycle reaches zero, it rotates the remaining indices and resets.

Implementing Permutations from Scratch

Recursive Approach

python

1def permutations_recursive(items):
2    if len(items) <= 1:
3        return [items]
4
5    result = []
6    for i, item in enumerate(items):
7        remaining = items[:i] + items[i+1:]
8        for perm in permutations_recursive(remaining):
9            result.append([item] + perm)
10    return result
11
12print(permutations_recursive([1, 2, 3]))
13# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Heap's Algorithm (In-Place)

Heap's algorithm generates permutations by swapping elements in place, minimizing the number of swaps:

python

1def heaps_permutations(arr):
2    result = []
3
4    def generate(k, arr):
5        if k == 1:
6            result.append(arr[:])
7            return
8        for i in range(k):
9            generate(k - 1, arr)
10            if k % 2 == 0:
11                arr[i], arr[k-1] = arr[k-1], arr[i]
12            else:
13                arr[0], arr[k-1] = arr[k-1], arr[0]
14
15    generate(len(arr), arr)
16    return result
17
18print(heaps_permutations([1, 2, 3]))

Practical Examples

Finding Anagrams

python

1from itertools import permutations
2
3def find_anagrams(word, dictionary):
4    perms = set(''.join(p) for p in permutations(word))
5    return perms & dictionary
6
7word_set = {'act', 'cat', 'tac', 'dog', 'god'}
8print(find_anagrams('cat', word_set))  # {'act', 'cat', 'tac'}

Brute-Force Shortest Path (TSP)

python

1from itertools import permutations
2
3def brute_force_tsp(distances):
4    """Find shortest path visiting all cities (small n only)."""
5    n = len(distances)
6    cities = list(range(1, n))  # Fix city 0 as start
7    best_cost = float('inf')
8    best_path = None
9
10    for perm in permutations(cities):
11        path = (0,) + perm + (0,)
12        cost = sum(distances[path[i]][path[i+1]] for i in range(n))
13        if cost < best_cost:
14            best_cost = cost
15            best_path = path
16
17    return best_path, best_cost

Generating Next Permutation

python

1def next_permutation(arr):
2    """Generate the lexicographically next permutation in place."""
3    n = len(arr)
4    # Find largest i where arr[i] < arr[i+1]
5    i = n - 2
6    while i >= 0 and arr[i] >= arr[i+1]:
7        i -= 1
8    if i < 0:
9        arr.reverse()
10        return False  # Wrapped around
11
12    # Find largest j where arr[j] > arr[i]
13    j = n - 1
14    while arr[j] <= arr[i]:
15        j -= 1
16
17    arr[i], arr[j] = arr[j], arr[i]
18    arr[i+1:] = reversed(arr[i+1:])
19    return True

Performance Considerations

n	Permutations (n!)	Time
5	120	Instant
8	40,320	Fast
10	3,628,800	~1 second
12	479,001,600	~2 minutes
15	1,307,674,368,000	Impractical

itertools.permutations is a C extension, so it is much faster than pure Python implementations. But factorial growth means anything beyond n=12 becomes impractical for exhaustive enumeration.

Common Pitfalls

Duplicate elements: itertools.permutations treats elements by position, not value. permutations([1, 1, 2]) yields (1, 1, 2) twice (once for each 1). For unique permutations, wrap in set() or use more_itertools.distinct_permutations.
Memory: list(permutations(range(12))) creates 479 million tuples and will exhaust memory. Iterate lazily instead of converting to a list.
Factorial explosion: n! grows extremely fast. For n > 12, consider heuristic or approximate algorithms instead of exhaustive permutation.
Strings produce tuples: permutations('abc') yields ('a', 'b', 'c') not 'abc'. Use ''.join(p) to get strings back.
Not sorted input: itertools.permutations generates permutations in the order of the input indices, not in lexicographic order of values. Sort the input first if you need lexicographic order.

Summary

itertools.permutations(iterable, r) generates r-length orderings lazily using a cycle-based index algorithm
The number of permutations is P(n, r) = n! / (n-r)! — grows factorially
Use itertools.permutations (C extension) over pure Python implementations for performance
For unique permutations of duplicates, use set() or more_itertools.distinct_permutations
Anything beyond n=12 is impractical for exhaustive enumeration — use heuristics instead