Introduction

Permutation generation is inherently expensive because the output itself is factorial in size. For n distinct elements, there are n! results, so no algorithm can avoid explosive growth at large n. Efficiency therefore means minimizing overhead per generated permutation and choosing generation order that matches your use case.

Start with the Right Objective

"Most efficient" depends on what you need:

• Enumerate every permutation once.
• Stop early when a condition is satisfied.
• Generate in lexicographic order.
• Minimize memory allocation.

If you must inspect all permutations, focus on constant factors and streaming style iteration. If early stopping is allowed, the best speedup usually comes from pruning, not from micro-optimizing generation itself.

Practical Baseline in Python

For Python, itertools.permutations is usually the best default. It is implemented in C and yields lazily.

1from itertools import permutations
2
3items = [1, 2, 3]
4for p in permutations(items):
5    print(p)

Why this baseline is strong:

• Lazy iterator avoids storing all results.
• Well-tested and stable behavior.
• Fast enough for most scripting and interview-scale tasks.

If you need results as list, convert explicitly, but remember memory blowup:

all_perms = list(permutations(range(8)))
print(len(all_perms))

Heap's Algorithm for In-Place Generation

Heap's algorithm is a classic choice when you want in-place swaps and minimal movement.

1def heaps_permutations(arr):
2    a = arr[:]  # keep caller data unchanged
3    n = len(a)
4    c = [0] * n
5    yield tuple(a)
6
7    i = 0
8    while i < n:
9        if c[i] < i:
10            if i % 2 == 0:
11                a[0], a[i] = a[i], a[0]
12            else:
13                a[c[i]], a[i] = a[i], a[c[i]]
14            yield tuple(a)
15            c[i] += 1
16            i = 0
17        else:
18            c[i] = 0
19            i += 1
20
21
22for p in heaps_permutations([1, 2, 3]):
23    print(p)

Properties:

• Generates each permutation exactly once.
• Uses O(n) auxiliary state.
• Performs simple swap operations, which is good for low-level implementations.

Lexicographic Generation with Next-Permutation

If output order matters, lexicographic generation is useful. The next-permutation operation transforms one arrangement into the next in dictionary order.

1def next_permutation(a):
2    i = len(a) - 2
3    while i >= 0 and a[i] >= a[i + 1]:
4        i -= 1
5    if i < 0:
6        return False
7
8    j = len(a) - 1
9    while a[j] <= a[i]:
10        j -= 1
11
12    a[i], a[j] = a[j], a[i]
13    a[i + 1:] = reversed(a[i + 1:])
14    return True
15
16
17a = [1, 2, 3]
18print(tuple(a))
19while next_permutation(a):
20    print(tuple(a))

This order is convenient when comparing against sorted references or implementing combinatorial search that assumes monotonic order.

Early Exit and Constraint Pruning

Real workloads often do not require full enumeration. Add checks early in the generation path.

1from itertools import permutations
2
3
4def find_first_with_prefix(items, prefix):
5    plen = len(prefix)
6    for p in permutations(items):
7        if p[:plen] == tuple(prefix):
8            return p
9    return None
10
11print(find_first_with_prefix([1, 2, 3, 4], [2, 1]))

For harder constraints, recursive backtracking with branch pruning can outperform full generators by several orders of magnitude.

Complexity Reality Check

For complete generation:

• Time is proportional to n! permutations.
• Space can stay near linear if emitted lazily.

For any claim of dramatic speed improvement, verify whether the algorithm is actually skipping work via pruning rather than merely generating faster.

Benchmarking the Right Way

Micro-benchmark on representative n and realistic stopping behavior.

1import time
2from itertools import permutations
3
4n = 9
5start = time.perf_counter()
6count = 0
7for _ in permutations(range(n)):
8    count += 1
9print(count, time.perf_counter() - start)

Always compare like-for-like output size and ordering constraints.

Common Pitfalls

• Trying to store all permutations in memory. Fix by consuming generator output incrementally.
• Ignoring factorial growth and testing only tiny inputs. Fix by estimating n! before implementation choices.
• Chasing custom code when standard library is already optimal enough. Fix by profiling first.
• Requiring lexicographic order but using algorithm with arbitrary order. Fix by selecting next-permutation or sorting outputs.
• Mixing duplicate elements without deduplication strategy. Fix by using set-aware generation or sorted skip logic.

Summary

• Permutation generation cost is dominated by factorial output size.
• In Python, itertools.permutations is the practical baseline.
• Heap's algorithm is efficient for swap-based in-place generation.
• Next-permutation is useful when lexicographic order is required.
• Major performance gains usually come from pruning and early exit, not minor per-step tweaks.