Generating All Permutations

Permutations are everywhere in computer science and everyday life. How many ways can you arrange books on a shelf? In how many orders can a scheduler execute tasks? How many distinct passwords can be formed from a set of characters? These questions all reduce to the same fundamental problem: generating all permutations of a set of elements.

A permutation is an ordered arrangement of elements. Given a set of n distinct elements, a permutation is a sequence containing each element exactly once. The number of such arrangements is n! (n factorial)—a quantity that grows explosively with n. For 3 elements, there are 6 permutations. For 10 elements, there are 3,628,800. For 20 elements, there are over 2.4 quintillion.

This explosive growth makes naively generating and storing all permutations infeasible for even moderately large inputs. Yet with backtracking, we can systematically explore the permutation space, generating each arrangement exactly once without redundant computation.

Before diving into algorithms, we must establish a rigorous mathematical foundation. Understanding the combinatorial structure of permutations illuminates why certain algorithmic approaches work and guides us toward efficient implementations.

Formal Definition:

A permutation of a set S = {a₁, a₂, ..., aₙ} is a bijective function π: {1, 2, ..., n} → {1, 2, ..., n}. Equivalently, it's an ordered tuple (π(1), π(2), ..., π(n)) where π(i) indicates the position of element aᵢ in the arrangement, or alternatively, aπ(i) is the element at position i.

For practical purposes, we represent a permutation as an ordered sequence of the elements themselves. Given [1, 2, 3], the permutations are:

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

Key Observations from the Growth Table:

1. Factorial grows faster than exponential. While 2ⁿ doubles with each increment of n, n! multiplies by an ever-larger factor. At n=20, n! dwarfs 2²⁰ (≈ 1 million) by a factor of over 2 trillion.

2. Practical limits are severe. Real-world permutation generation is feasible only for small n—typically n ≤ 10-12 for interactive applications, and perhaps n ≤ 15-18 with significant computational resources.

3. This constrains algorithm design. Since we must generate n! outputs, no clever algorithm can do better than O(n!) for exhaustive generation. Our goal is to achieve O(n!) with minimal overhead—ideally O(n) per permutation or O(n × n!) total.

Lexicographic Ordering:

Permutations have a natural ordering when we treat them as numbers or strings. The lexicographic order (dictionary order) arranges permutations such that [1,2,3] < [1,3,2] < [2,1,3] < ... < [3,2,1]. This ordering provides a deterministic sequence through all permutations and is often the expected output format.

Generating all permutations fits perfectly into the backtracking framework. The problem exhibits a clear decision tree structure where:

1. At each level, we decide which element to place in the current position
2. Each branch represents choosing a specific element
3. Leaf nodes represent complete permutations
4. Backtracking occurs when we return from a completed permutation to explore alternative choices

The Decision Tree Perspective:

Consider generating permutations of [1, 2, 3]. The decision tree looks like this:

                    [start]
                   /   |   
                  1    2    3        ← Choose first element
                 / \  / \  / 
                2   3 1  3 1  2      ← Choose second element
                |   | |  | |  |
                3   2 3  1 2  1      ← Only one choice remains

Each root-to-leaf path generates exactly one permutation. The tree has n! leaves (one per permutation) and the total number of nodes is bounded by n × n!.

Why Not Other Paradigms?

Why not iterative enumeration? While possible (Heap's algorithm, next-permutation iteration), recursive backtracking is more intuitive, easier to modify for variants, and naturally extends to constrained permutations.

Why not divide-and-conquer? Permutations don't decompose into independent subproblems the way sorting does. The choice for position 1 affects all subsequent choices.

Why not dynamic programming? There's no overlapping subproblem structure. Each permutation is unique, and computing one doesn't help compute another.

Why not greedy? There's no 'best' choice at each step—we need all choices, not a single optimal one.

Backtracking is thus the natural fit: we're systematically exploring a search space, generating all valid configurations, with no pruning possible (every permutation is valid).

The most straightforward implementation uses an auxiliary boolean array to track which elements have been used. This approach is pedagogically clear and works for any type of elements, not just integers.

Algorithm Overview:

1. Maintain a current array representing the partial permutation
2. Maintain a used boolean array marking which elements are already in current
3. At each recursive call, try each unused element in the current position
4. Mark it as used, recurse to fill remaining positions, then unmark it
5. When current has n elements, record the complete permutation

Detailed Execution Trace:

Let's trace through the algorithm for input [A, B, C]:

backtrack() called with current=[], used=[F,F,F]
  i=0: Choose A → current=[A], used=[T,F,F]
    backtrack() called with current=[A], used=[T,F,F]
      i=0: A is used, skip
      i=1: Choose B → current=[A,B], used=[T,T,F]
        backtrack() called with current=[A,B], used=[T,T,F]
          i=0,1: used, skip
          i=2: Choose C → current=[A,B,C], used=[T,T,T]
            backtrack() → length=3 → RECORD [A,B,C]
          Unchoose C → current=[A,B], used=[T,T,F]
        return
      Unchoose B → current=[A], used=[T,F,F]
      i=2: Choose C → current=[A,C], used=[T,F,T]
        backtrack() → ... → RECORD [A,C,B]
      Unchoose C → current=[A], used=[T,F,F]
    return
  Unchoose A → current=[], used=[F,F,F]
  i=1: Choose B → ... → RECORD [B,A,C], [B,C,A]
  i=2: Choose C → ... → RECORD [C,A,B], [C,B,A]

Complexity Analysis:

Time Complexity: O(n × n!)

• We generate n! permutations
• Each permutation requires O(n) work to copy into results
• The recursion itself: at depth d, we iterate through n elements, checking used[i] and potentially recursing. The total recursive calls equal the nodes in the decision tree, which is O(n × n!)

Space Complexity: O(n) for the recursion (excluding output storage)

• used array: O(n)
• current array: O(n)
• Recursion stack depth: O(n)
• Output storage: O(n × n!) for all permutations

Per-Permutation Overhead: O(n) for copying the result array.

An elegant alternative to the 'used' array approach is to generate permutations in-place using swaps. Instead of building a separate current array and tracking used elements, we permute the original array directly by systematically swapping elements.

Key Insight:

Consider the array as divided into two regions:

• Positions [0, index-1]: Fixed prefix (already chosen)
• Positions [index, n-1]: Remaining elements to permute

At each step, we select one element from the remaining region to place at position index by swapping it with whatever is currently at index. After recursing to handle positions [index+1, n-1], we swap back to restore the original state.

The Invariant:

At recursion depth index, positions [0, index-1] are fixed for this branch, and all elements originally in the array are still present—just in different positions. The region [index, n-1] contains exactly the elements not in the fixed prefix.

Trace Output for [1, 2, 3]:

backtrack(index=0), arr=[1,2,3]
Swap positions 0 ↔ 0
  backtrack(index=1), arr=[1,2,3]
  Swap positions 1 ↔ 1
    backtrack(index=2), arr=[1,2,3]
    Swap positions 2 ↔ 2
      backtrack(index=3), arr=[1,2,3]
      → RECORD: [1,2,3]
    Restored arr=[1,2,3]
  Restored arr=[1,2,3]
  Swap positions 1 ↔ 2
    backtrack(index=2), arr=[1,3,2]
    Swap positions 2 ↔ 2
      backtrack(index=3), arr=[1,3,2]
      → RECORD: [1,3,2]
    ...

Advantages of the Swap Approach:

1. No auxiliary 'used' array — We avoid the O(n) overhead of tracking used elements
2. True in-place permutation — The array itself is permuted (though we copy for results)
3. Slightly less memory — No boolean array allocation
4. Natural for certain variants — Some problems (like finding a specific permutation) work well with swaps

Disadvantages:

1. Non-lexicographic order — The output order differs from dictionary order (see below)
2. Less intuitive — The swapping logic can be harder to reason about initially
3. Modifies array state — Requires careful restoration during backtracking

For any algorithmic procedure, especially recursive ones, we should rigorously establish correctness. For permutation generation, we must prove two properties:

1. Soundness: Every output is a valid permutation (contains each element exactly once)
2. Completeness: Every possible permutation is generated exactly once

Soundness Proof (Using 'Used' Array Approach):

Claim: At the base case when current.length === n, current contains exactly the n input elements, each appearing exactly once.

Proof by induction on current.length:

Base case: When current.length = 0, no elements are in current and used[i] = false for all i. The invariant holds vacuously.

Inductive hypothesis: Assume when current.length = k, current contains k distinct elements from the input, and used[i] = true if and only if elements[i] is in current.

Inductive step: When we add an element:

• We only add elements[i] if !used[i] (not already in current)
• After adding, we set used[i] = true
• Now current.length = k+1 with k+1 distinct elements
• The invariant is maintained

At current.length = n, all n elements are in current, each exactly once. ∎

Completeness Proof:

Claim: Every permutation of the input is generated exactly once.

Proof:

Consider any permutation P = (p₁, p₂, ..., pₙ). We show the algorithm visits P exactly once.

Existence: At each depth k, the algorithm iterates through all unused elements. Since P is a permutation, pₖ is an element not used by (p₁, ..., pₖ₋₁). Thus, when filling position k, the algorithm will eventually try pₖ. By induction, the path through the recursion tree corresponding to P's construction will be traversed.

Uniqueness: The algorithm's structure ensures no permutation is generated twice. Each permutation corresponds to a unique path from root to leaf in the decision tree. Different paths generate different sequences of choices, producing different permutations. ∎

Corollary: The algorithm generates exactly n! permutations.

Proof: By completeness, all n! permutations are generated. By soundness, every output is a valid permutation. Since each valid permutation appears exactly once, the count is exactly n!. ∎

Many applications require permutations in lexicographic (dictionary) order. For a sorted input, the 'used' array approach naturally produces sorted output because we iterate through elements in their original order and choose the smallest available at each position.

Ensuring Lexicographic Order:

The 'used' array method produces lexicographic output if and only if the input is sorted. The first element chosen at each position is the smallest unused, leading to the lexicographically smallest permutation starting with that prefix.

Why the Swap Method Fails:

The swap method disrupts element ordering in the suffix. After swapping element at position 0 with element at position 2, the suffix is now [original[0], original[2]] with elements potentially out of order. Subsequent iterations don't select the smallest available element.

Forcing Lexicographic Order with Swaps:

One can modify the swap approach to restore sorted order in the suffix after each choice, but this adds O(n log n) overhead per choice, making it less efficient than the used-array approach.

The Next-Permutation Algorithm:

An alternative for generating lexicographic permutations is the next-permutation algorithm, which transforms the current permutation into its lexicographic successor in O(n) time. This is useful when you need to:

• Iterate through permutations without storing all of them
• Resume enumeration from a specific permutation
• Generate permutations iteratively rather than recursively

The algorithm works by:

1. Finding the rightmost element smaller than its successor (the 'pivot')
2. Finding the rightmost element larger than the pivot
3. Swapping them
4. Reversing the suffix after the pivot position

If no pivot exists (the array is the last permutation), return an indicator that enumeration is complete.

When implementing permutation generation in production systems, several practical factors influence algorithm choice and implementation details.

Memory Management:

Storing all n! permutations is often infeasible. For n = 12, just storing the permutations (without any overhead) requires about 5.8 GB. Alternative strategies:

1. Generator/Iterator Pattern: Yield permutations one at a time, processing each before generating the next
2. Callback Approach: Pass a callback function to process each permutation immediately
3. Lazy Evaluation: Use iterators that compute permutations on-demand
4. Streaming: Process permutations without retaining them in memory