Data Structures & AlgorithmsBacktracking — Systematic Exploration

Permutations & Combinations

LevelIntermediate

Duration90 mins

TopicBacktracking — Systematic Exploration

1 / 4

Generating All Permutations

The Fundamental Problem of Arrangement

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.

What You Will Master

By the end of this page, you will deeply understand:

• The mathematical structure underlying permutations • Why backtracking is the natural paradigm for permutation generation • Multiple implementation strategies with their tradeoffs • How to reason about correctness and completeness • Performance characteristics and optimization opportunities

Mathematical Foundations of Permutations

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)

The Counting Principle

The number of permutations of n distinct elements is n! (n factorial), computed as n × (n-1) × (n-2) × ... × 2 × 1.

Intuition: For the first position, we have n choices. For the second, n-1 remain. For the third, n-2, and so on until only one element remains for the last position. By the multiplication principle: n × (n-1) × ... × 1 = n!

Factorial Growth: Number of Permutations
n	n! (Permutations)	Approximate Time at 10⁶ ops/sec
3	6	6 microseconds
5	120	120 microseconds
8	40,320	40 milliseconds
10	3,628,800	3.6 seconds
12	479,001,600	8 minutes
15	1,307,674,368,000	15 days
20	2,432,902,008,176,640,000	77 million years

Key Observations from the Growth Table:

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.
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.
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.

Properties of Permutations

•Cardinality: |P(S)| = n! for a set S with n distinct elements
•Bijection: Each permutation is a one-to-one correspondence from positions to elements
•Group Structure: Permutations form a group under composition (the symmetric group Sₙ)
•Inversion Count: The minimum number of adjacent swaps to reach sorted order—a measure of 'disorder'
•Parity: Permutations are classified as even or odd based on whether they can be achieved by an even or odd number of transpositions

Why Backtracking is the Natural Paradigm

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

At each level, we decide which element to place in the current position
Each branch represents choosing a specific element
Leaf nodes represent complete permutations
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!.

The Backtracking Template Applied

The universal backtracking template maps directly to permutation generation:

Choose: Select an unused element for the current position Explore: Recursively fill remaining positions Unchoose: Mark the element as available again (backtrack)

This pattern ensures we explore all branches while maintaining the invariant that each element appears exactly once in the current partial solution.

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).

Backtracking Invariants for Permutations

•Partial Solution Validity: At any point, the current sequence contains distinct elements only
•Element Availability: Each element is either 'used' (in the current sequence) or 'available'
•Position Progress: We fill positions from left to right (or equivalently, from position 0 to n-1)
•Completeness: A permutation is complete when all n positions are filled
•Exhaustiveness: Every valid element choice is explored at each decision point

The Classic 'Used' Array Implementation

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:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function generatePermutations<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function backtrack(): void {
        // Base case: complete permutation found
        if (current.length === n) {
            results.push([...current]); // Copy to avoid mutation
            return;
        }
        
        // Try each unused element in the current position
        for (let i = 0; i < n; i++) {
            if (used[i]) continue; // Skip already-used elements
            
            // Choose: add element to current permutation
            current.push(elements[i]);
            used[i] = true;
            
            // Explore: recursively fill remaining positions
            backtrack();
            
            // Unchoose: remove element and mark as available
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Example usage
const input = [1, 2, 3];
const perms = generatePermutations(input);
console.log("Permutations of [1,2,3]:");
perms.forEach(p => console.log(p.join(", ")));
 
// Output:
// 1, 2, 3
// 1, 3, 2
// 2, 1, 3
// 2, 3, 1
// 3, 1, 2
// 3, 2, 1

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]

The Critical Copy Step

Notice results.push([...current]) makes a copy of the current array. This is essential! Without the copy, all entries in results would reference the same array, which ends up empty after all backtracking completes. This is a common source of bugs in backtracking implementations.

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.

The Swap-Based Approach

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
function permuteBySwapping<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const arr = [...elements]; // Work on a copy to preserve input
    
    function backtrack(index: number): void {
        // Base case: all positions fixed
        if (index === arr.length) {
            results.push([...arr]); // Record current arrangement
            return;
        }
        
        // Try each element from index onwards at position 'index'
        for (let i = index; i < arr.length; i++) {
            // Choose: swap element at 'i' to position 'index'
            [arr[index], arr[i]] = [arr[i], arr[index]];
            
            // Explore: fix position 'index' and permute the rest
            backtrack(index + 1);
            
            // Unchoose: swap back to restore original arrangement
            [arr[index], arr[i]] = [arr[i], arr[index]];
        }
    }
    
    backtrack(0);
    return results;
}
 
// Example with tracing
function permuteWithTrace<T>(elements: T[]): void {
    const arr = [...elements];
    const indent = (d: number) => "  ".repeat(d);
    
    function backtrack(index: number, depth: number): void {
        console.log(`${indent(depth)}backtrack(index=${index}), arr=[${arr.join(",")}]`);
        
        if (index === arr.length) {
            console.log(`${indent(depth)}→ RECORD: [${arr.join(",")}]`);
            return;
        }
        
        for (let i = index; i < arr.length; i++) {
            console.log(`${indent(depth)}Swap positions ${index} ↔ ${i}`);
            [arr[index], arr[i]] = [arr[i], arr[index]];
            backtrack(index + 1, depth + 1);
            [arr[index], arr[i]] = [arr[i], arr[index]];
            console.log(`${indent(depth)}Restored arr=[${arr.join(",")}]`);
        }
    }
    
    backtrack(0, 0);
}
 
permuteWithTrace([1, 2, 3]);

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:

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

Disadvantages:

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

Non-Lexicographic Output Order

The swap-based approach does not produce permutations in lexicographic order. For [1,2,3], it produces: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]. Notice [3,2,1] appears before [3,1,2], which is incorrect for lexicographic ordering. If sorted output is required, either sort the results afterward or use a different algorithm.

Proving Correctness and Completeness

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

Soundness: Every output is a valid permutation (contains each element exactly once)
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!. ∎

Why Proofs Matter in Practice

You might wonder why we prove such 'obvious' properties. In practice:

Proofs reveal invariants that must be maintained when modifying the algorithm
They catch subtle bugs — a broken invariant leads to proof failure
They guide extensions — to handle duplicates, constraints, or k-permutations, we adapt the proof
They build confidence — knowing the algorithm is correct prevents debugging wild goose chases

Generating Permutations in Lexicographic Order

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function permuteLexicographic<T>(elements: T[]): T[][] {
    // Sort input to ensure lexicographic output
    const sorted = [...elements].sort((a, b) => {
        if (a < b) return -1;
        if (a > b) return 1;
        return 0;
    });
    
    const results: T[][] = [];
    const n = sorted.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        // Iterate in sorted order ensures lexicographic output
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            current.push(sorted[i]);
            used[i] = true;
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Verify lexicographic order
const chars = ["c", "a", "b"];
console.log("Lexicographic permutations of ['c','a','b']:");
permuteLexicographic(chars).forEach((p, i) => {
    console.log(`${i + 1}: ${p.join("")}`);
});
 
// Output:
// 1: abc
// 2: acb
// 3: bac
// 4: bca
// 5: cab
// 6: cba

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:

Finding the rightmost element smaller than its successor (the 'pivot')
Finding the rightmost element larger than the pivot
Swapping them
Reversing the suffix after the pivot position

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function nextPermutation<T>(arr: T[]): boolean {
    const n = arr.length;
    
    // Step 1: Find the rightmost element smaller than its successor
    let pivot = n - 2;
    while (pivot >= 0 && arr[pivot] >= arr[pivot + 1]) {
        pivot--;
    }
    
    // No pivot found means this is the last permutation
    if (pivot < 0) return false;
    
    // Step 2: Find rightmost element greater than pivot
    let successor = n - 1;
    while (arr[successor] <= arr[pivot]) {
        successor--;
    }
    
    // Step 3: Swap pivot with successor
    [arr[pivot], arr[successor]] = [arr[successor], arr[pivot]];
    
    // Step 4: Reverse suffix after pivot
    let left = pivot + 1;
    let right = n - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
    
    return true;
}
 
// Generate all permutations iteratively
function allPermutationsIterative<T>(elements: T[]): T[][] {
    const arr = [...elements].sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
    const results: T[][] = [];
    
    do {
        results.push([...arr]);
    } while (nextPermutation(arr));
    
    return results;
}
 
console.log("Iterative generation of [1,2,3] permutations:");
allPermutationsIterative([1, 2, 3]).forEach(p => console.log(p));

Practical Considerations and Performance Optimization

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:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function* permuteGenerator<T>(elements: T[]): Generator<T[], void, unknown> {
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function* backtrack(): Generator<T[], void, unknown> {
        if (current.length === n) {
            yield [...current]; // Yield each permutation
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            current.push(elements[i]);
            used[i] = true;
            yield* backtrack(); // Delegate to recursive generator
            current.pop();
            used[i] = false;
        }
    }
    
    yield* backtrack();
}
 
// Usage: Process permutations one at a time
console.log("Processing permutations without storing all:");
let count = 0;
for (const perm of permuteGenerator([1, 2, 3, 4])) {
    count++;
    if (count <= 3) console.log(`Permutation ${count}: [${perm}]`);
}
console.log(`Total permutations processed: ${count}`);
 
// Can also stop early
console.log("\nFinding first permutation ending with 4:");
for (const perm of permuteGenerator([1, 2, 3, 4])) {
    if (perm[perm.length - 1] === 4) {
        console.log(`Found: [${perm}]`);
        break;
    }
}

Performance Optimization Techniques

•Avoid array copying when possible: If you only need to check properties of permutations, work with current directly instead of copying
•Use typed arrays for numbers: Int32Array or Uint8Array can be faster than generic arrays for numerical elements
•Pre-allocate arrays: Avoid repeated allocation by reusing fixed-size arrays
•Tail-call optimization: Some JavaScript engines optimize tail-recursive calls; restructure if applicable
•Iterative Heap's Algorithm: For pure generation speed without caring about order, Heap's algorithm minimizes swaps (each permutation differs by exactly one swap)
•Parallelization: For large n, partition the work by fixing the first k elements and processing in parallel

Heap's Algorithm: Minimal-Swap Generation

Heap's Algorithm generates permutations such that consecutive permutations differ by exactly one swap. This minimizes array manipulation and can be implemented non-recursively with O(1) extra space (beyond the array itself). It's the theoretically optimal algorithm for raw permutation enumeration speed, but produces non-lexicographic order.

Summary and Looking Forward

We've explored the fundamental problem of generating all permutations through the lens of backtracking. Let's consolidate the key insights:

Core Concepts:

Permutations are ordered arrangements of elements; n elements yield n! permutations
Backtracking naturally models permutation generation as a decision tree exploration
The 'choose-explore-unchoose' template applies directly: choose an element, recurse, undo

Implementation Approaches:

Used-array method: Clear, intuitive, produces lexicographic order with sorted input
Swap-based method: In-place, no auxiliary tracking, but non-lexicographic order
Next-permutation: Iterative, memory-efficient, lexicographic, O(n) per permutation
Generator pattern: Memory-efficient, allows early termination and streaming

Key Takeaways

•Factorial growth limits problem size — Always consider whether exhaustive generation is feasible before implementing
•Both soundness and completeness matter — Proving your algorithm generates all permutations exactly once prevents subtle bugs
•Memory often dominates — Use generators or callbacks when results don't need to be retained
•Order requirements affect algorithm choice — Need lexicographic? Use the used-array approach with sorted input
•The pattern extends — The same backtracking structure handles k-permutations, constrained permutations, and permutations with duplicates (upcoming pages)

What's Next:

In the following pages, we'll extend this foundation to:

K-Combinations: Selecting k elements from n without regard to order—a related but distinct problem with its own backtracking structure
Swapping vs Inserting Approaches: Deep comparison of the two primary strategies and when each excels
Handling Duplicates: When elements repeat, naive algorithms produce duplicate permutations—we'll learn elegant techniques to avoid this without post-filtering

Page Complete

You now possess a comprehensive understanding of permutation generation through backtracking. You can implement multiple approaches, reason about their correctness, analyze their complexity, and choose appropriately for practical constraints. This foundation extends naturally to the combination problems we'll explore next.

1 / 4

Loading learning content...

Data Structures & AlgorithmsBacktracking — Systematic Exploration

Permutations & Combinations

LevelIntermediate

Duration90 mins

TopicBacktracking — Systematic Exploration

1 / 4

Generating All Permutations

The Fundamental Problem of Arrangement

What You Will Master

By the end of this page, you will deeply understand:

Mathematical Foundations of Permutations

Formal Definition:

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)

The Counting Principle

The number of permutations of n distinct elements is n! (n factorial), computed as n × (n-1) × (n-2) × ... × 2 × 1.

Factorial Growth: Number of Permutations
n	n! (Permutations)	Approximate Time at 10⁶ ops/sec
3	6	6 microseconds
5	120	120 microseconds
8	40,320	40 milliseconds
10	3,628,800	3.6 seconds
12	479,001,600	8 minutes
15	1,307,674,368,000	15 days
20	2,432,902,008,176,640,000	77 million years

Key Observations from the Growth Table:

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.
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.
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:

Properties of Permutations

•Cardinality: |P(S)| = n! for a set S with n distinct elements
•Bijection: Each permutation is a one-to-one correspondence from positions to elements
•Group Structure: Permutations form a group under composition (the symmetric group Sₙ)
•Inversion Count: The minimum number of adjacent swaps to reach sorted order—a measure of 'disorder'
•Parity: Permutations are classified as even or odd based on whether they can be achieved by an even or odd number of transpositions

Why Backtracking is the Natural Paradigm

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

At each level, we decide which element to place in the current position
Each branch represents choosing a specific element
Leaf nodes represent complete permutations
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!.

The Backtracking Template Applied

The universal backtracking template maps directly to permutation generation:

Choose: Select an unused element for the current position Explore: Recursively fill remaining positions Unchoose: Mark the element as available again (backtrack)

This pattern ensures we explore all branches while maintaining the invariant that each element appears exactly once in the current partial solution.

Why Not Other Paradigms?

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).

Backtracking Invariants for Permutations

•Partial Solution Validity: At any point, the current sequence contains distinct elements only
•Element Availability: Each element is either 'used' (in the current sequence) or 'available'
•Position Progress: We fill positions from left to right (or equivalently, from position 0 to n-1)
•Completeness: A permutation is complete when all n positions are filled
•Exhaustiveness: Every valid element choice is explored at each decision point

The Classic 'Used' Array Implementation

Algorithm Overview:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function generatePermutations<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function backtrack(): void {
        // Base case: complete permutation found
        if (current.length === n) {
            results.push([...current]); // Copy to avoid mutation
            return;
        }
        
        // Try each unused element in the current position
        for (let i = 0; i < n; i++) {
            if (used[i]) continue; // Skip already-used elements
            
            // Choose: add element to current permutation
            current.push(elements[i]);
            used[i] = true;
            
            // Explore: recursively fill remaining positions
            backtrack();
            
            // Unchoose: remove element and mark as available
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Example usage
const input = [1, 2, 3];
const perms = generatePermutations(input);
console.log("Permutations of [1,2,3]:");
perms.forEach(p => console.log(p.join(", ")));
 
// Output:
// 1, 2, 3
// 1, 3, 2
// 2, 1, 3
// 2, 3, 1
// 3, 1, 2
// 3, 2, 1

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]

The Critical Copy Step

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.

The Swap-Based Approach

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

The Invariant:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
function permuteBySwapping<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const arr = [...elements]; // Work on a copy to preserve input
    
    function backtrack(index: number): void {
        // Base case: all positions fixed
        if (index === arr.length) {
            results.push([...arr]); // Record current arrangement
            return;
        }
        
        // Try each element from index onwards at position 'index'
        for (let i = index; i < arr.length; i++) {
            // Choose: swap element at 'i' to position 'index'
            [arr[index], arr[i]] = [arr[i], arr[index]];
            
            // Explore: fix position 'index' and permute the rest
            backtrack(index + 1);
            
            // Unchoose: swap back to restore original arrangement
            [arr[index], arr[i]] = [arr[i], arr[index]];
        }
    }
    
    backtrack(0);
    return results;
}
 
// Example with tracing
function permuteWithTrace<T>(elements: T[]): void {
    const arr = [...elements];
    const indent = (d: number) => "  ".repeat(d);
    
    function backtrack(index: number, depth: number): void {
        console.log(`${indent(depth)}backtrack(index=${index}), arr=[${arr.join(",")}]`);
        
        if (index === arr.length) {
            console.log(`${indent(depth)}→ RECORD: [${arr.join(",")}]`);
            return;
        }
        
        for (let i = index; i < arr.length; i++) {
            console.log(`${indent(depth)}Swap positions ${index} ↔ ${i}`);
            [arr[index], arr[i]] = [arr[i], arr[index]];
            backtrack(index + 1, depth + 1);
            [arr[index], arr[i]] = [arr[i], arr[index]];
            console.log(`${indent(depth)}Restored arr=[${arr.join(",")}]`);
        }
    }
    
    backtrack(0, 0);
}
 
permuteWithTrace([1, 2, 3]);

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:

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

Disadvantages:

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

Non-Lexicographic Output Order

Proving Correctness and Completeness

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

Soundness: Every output is a valid permutation (contains each element exactly once)
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.

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!. ∎

Why Proofs Matter in Practice

You might wonder why we prove such 'obvious' properties. In practice:

Proofs reveal invariants that must be maintained when modifying the algorithm
They catch subtle bugs — a broken invariant leads to proof failure
They guide extensions — to handle duplicates, constraints, or k-permutations, we adapt the proof
They build confidence — knowing the algorithm is correct prevents debugging wild goose chases

Generating Permutations in Lexicographic Order

Ensuring Lexicographic Order:

Why the Swap Method Fails:

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function permuteLexicographic<T>(elements: T[]): T[][] {
    // Sort input to ensure lexicographic output
    const sorted = [...elements].sort((a, b) => {
        if (a < b) return -1;
        if (a > b) return 1;
        return 0;
    });
    
    const results: T[][] = [];
    const n = sorted.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        // Iterate in sorted order ensures lexicographic output
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            current.push(sorted[i]);
            used[i] = true;
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Verify lexicographic order
const chars = ["c", "a", "b"];
console.log("Lexicographic permutations of ['c','a','b']:");
permuteLexicographic(chars).forEach((p, i) => {
    console.log(`${i + 1}: ${p.join("")}`);
});
 
// Output:
// 1: abc
// 2: acb
// 3: bac
// 4: bca
// 5: cab
// 6: cba

The Next-Permutation Algorithm:

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

The algorithm works by:

Finding the rightmost element smaller than its successor (the 'pivot')
Finding the rightmost element larger than the pivot
Swapping them
Reversing the suffix after the pivot position

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
function nextPermutation<T>(arr: T[]): boolean {
    const n = arr.length;
    
    // Step 1: Find the rightmost element smaller than its successor
    let pivot = n - 2;
    while (pivot >= 0 && arr[pivot] >= arr[pivot + 1]) {
        pivot--;
    }
    
    // No pivot found means this is the last permutation
    if (pivot < 0) return false;
    
    // Step 2: Find rightmost element greater than pivot
    let successor = n - 1;
    while (arr[successor] <= arr[pivot]) {
        successor--;
    }
    
    // Step 3: Swap pivot with successor
    [arr[pivot], arr[successor]] = [arr[successor], arr[pivot]];
    
    // Step 4: Reverse suffix after pivot
    let left = pivot + 1;
    let right = n - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
    
    return true;
}
 
// Generate all permutations iteratively
function allPermutationsIterative<T>(elements: T[]): T[][] {
    const arr = [...elements].sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
    const results: T[][] = [];
    
    do {
        results.push([...arr]);
    } while (nextPermutation(arr));
    
    return results;
}
 
console.log("Iterative generation of [1,2,3] permutations:");
allPermutationsIterative([1, 2, 3]).forEach(p => console.log(p));

Practical Considerations and Performance Optimization

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:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function* permuteGenerator<T>(elements: T[]): Generator<T[], void, unknown> {
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function* backtrack(): Generator<T[], void, unknown> {
        if (current.length === n) {
            yield [...current]; // Yield each permutation
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            current.push(elements[i]);
            used[i] = true;
            yield* backtrack(); // Delegate to recursive generator
            current.pop();
            used[i] = false;
        }
    }
    
    yield* backtrack();
}
 
// Usage: Process permutations one at a time
console.log("Processing permutations without storing all:");
let count = 0;
for (const perm of permuteGenerator([1, 2, 3, 4])) {
    count++;
    if (count <= 3) console.log(`Permutation ${count}: [${perm}]`);
}
console.log(`Total permutations processed: ${count}`);
 
// Can also stop early
console.log("\nFinding first permutation ending with 4:");
for (const perm of permuteGenerator([1, 2, 3, 4])) {
    if (perm[perm.length - 1] === 4) {
        console.log(`Found: [${perm}]`);
        break;
    }
}

Performance Optimization Techniques

•Avoid array copying when possible: If you only need to check properties of permutations, work with current directly instead of copying
•Use typed arrays for numbers: Int32Array or Uint8Array can be faster than generic arrays for numerical elements
•Pre-allocate arrays: Avoid repeated allocation by reusing fixed-size arrays
•Tail-call optimization: Some JavaScript engines optimize tail-recursive calls; restructure if applicable
•Iterative Heap's Algorithm: For pure generation speed without caring about order, Heap's algorithm minimizes swaps (each permutation differs by exactly one swap)
•Parallelization: For large n, partition the work by fixing the first k elements and processing in parallel

Heap's Algorithm: Minimal-Swap Generation

Summary and Looking Forward

We've explored the fundamental problem of generating all permutations through the lens of backtracking. Let's consolidate the key insights:

Core Concepts:

Permutations are ordered arrangements of elements; n elements yield n! permutations
Backtracking naturally models permutation generation as a decision tree exploration
The 'choose-explore-unchoose' template applies directly: choose an element, recurse, undo

Implementation Approaches:

Used-array method: Clear, intuitive, produces lexicographic order with sorted input
Swap-based method: In-place, no auxiliary tracking, but non-lexicographic order
Next-permutation: Iterative, memory-efficient, lexicographic, O(n) per permutation
Generator pattern: Memory-efficient, allows early termination and streaming

Key Takeaways

•Factorial growth limits problem size — Always consider whether exhaustive generation is feasible before implementing
•Both soundness and completeness matter — Proving your algorithm generates all permutations exactly once prevents subtle bugs
•Memory often dominates — Use generators or callbacks when results don't need to be retained
•Order requirements affect algorithm choice — Need lexicographic? Use the used-array approach with sorted input
•The pattern extends — The same backtracking structure handles k-permutations, constrained permutations, and permutations with duplicates (upcoming pages)

What's Next:

In the following pages, we'll extend this foundation to:

K-Combinations: Selecting k elements from n without regard to order—a related but distinct problem with its own backtracking structure
Swapping vs Inserting Approaches: Deep comparison of the two primary strategies and when each excels
Handling Duplicates: When elements repeat, naive algorithms produce duplicate permutations—we'll learn elegant techniques to avoid this without post-filtering

Page Complete

1 / 4