Permutations And Combinations - Learning Module

Loading content...

0/279

Swapping vs Inserting Approaches

Two Philosophies of Arrangement

When generating permutations programmatically, two fundamentally different strategies emerge from the algorithmic toolkit. The inserting (building) approach constructs permutations by progressively adding elements to a growing structure, while the swapping (rearranging) approach transforms permutations by exchanging elements within the original array.

These aren't merely implementation details—they represent distinct conceptual models that affect correctness reasoning, output ordering, memory usage, and adaptability to problem variants. A master algorithm designer understands both approaches deeply and selects the appropriate one based on problem constraints.

This page provides an exhaustive comparison, examining the mechanics, invariants, performance characteristics, and situational advantages of each paradigm. By the end, you'll have the judgment to choose wisely for any permutation-generation scenario.

What You Will Master

By the end of this page, you will understand:

• The fundamental mechanics of swapping vs inserting approaches • How each approach maintains its correctness invariants • The tradeoffs in memory, speed, output order, and extensibility • When to choose one approach over the other • Advanced variations like Heap's Algorithm and Steinhaus-Johnson-Trotter

The Inserting (Building) Approach

The inserting approach (also called the building or selection approach) constructs each permutation by progressively selecting elements from the available pool and adding them to a growing partial permutation. This is the approach we explored in depth for the 'used array' method.

Conceptual Model:

Imagine arranging books on a shelf, one at a time:

Start with an empty shelf (empty partial permutation)
Pick any book from the pile (select an unused element)
Place it in the next available position on the shelf (append to partial permutation)
Repeat until all books are placed (all elements used)
Record the arrangement, then try alternative book orderings (backtrack)

Key Characteristics:

Separation: The source (input) and destination (current permutation) are distinct structures
Tracking: An auxiliary mechanism tracks which elements have been used
Growth: The partial permutation grows from length 0 to length n
Order Preservation: Elements maintain their relative positions in the output based on selection sequence

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
function permuteByInserting<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    
    // Track which elements have been used
    const used: boolean[] = new Array(n).fill(false);
    
    // Build the permutation element by element
    const current: T[] = [];
    
    function backtrack(): void {
        // Base case: all elements placed
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        // Try each unused element in the current position
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            // SELECT: Mark element as used and add to permutation
            used[i] = true;
            current.push(elements[i]);
            
            // RECURSE: Fill remaining positions
            backtrack();
            
            // DESELECT: Restore availability and remove from permutation
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Visualize the decision tree
function permuteWithVisualization<T>(elements: T[]): void {
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    let callCount = 0;
    
    function backtrack(depth: number): void {
        callCount++;
        const indent = "  ".repeat(depth);
        const usedStr = used.map((u, i) => u ? elements[i] : "_").join(",");
        
        console.log(`${indent}Call #${callCount}: current=[${current}], used={${usedStr}}`);
        
        if (current.length === n) {
            console.log(`${indent}→ FOUND: [${current}]`);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            console.log(`${indent}Trying element ${elements[i]} at position ${current.length}`);
            used[i] = true;
            current.push(elements[i]);
            
            backtrack(depth + 1);
            
            current.pop();
            used[i] = false;
            console.log(`${indent}Backtracked from ${elements[i]}`);
        }
    }
    
    backtrack(0);
    console.log(`
Total recursive calls: ${callCount}`);
}
 
console.log("Permutations of [A, B, C] with visualization:");
permuteWithVisualization(["A", "B", "C"]);

Invariants of the Inserting Approach

•Element Coverage: used[i] = true ⟺ elements[i] ∈ current
•Progress: |current| = depth of recursion = number of true values in used
•Distinctness: All elements in current are distinct (enforced by used check)
•Completeness: At depth n, current contains exactly the n elements, each once
•Order: Elements appear in current in the order they were selected (not necessarily original order)

Lexicographic Order Property

When the input array is sorted and we iterate indices in order (0 to n-1), the inserting approach naturally produces permutations in lexicographic (dictionary) order. This is because at each position, we try smaller elements before larger ones.

The Swapping (Rearranging) Approach

The swapping approach generates permutations by rearranging elements within the original array through a sequence of swaps. Instead of building a separate structure, we transform the array in-place, record each configuration, and continue transforming.

Conceptual Model:

Imagine shuffling numbered cards on a table:

Cards start in their original positions
For position 0, try swapping with every card from positions 0 to n-1
After each swap, fix position 0 and recursively permute positions 1 to n-1
After exploring, swap back to restore for the next trial
When all positions are fixed (base case), record the arrangement

Key Characteristics:

In-place: Operations modify the single array (or a copy thereof)
No auxiliary tracking: Position naturally encodes 'used vs remaining'
Partition: Array conceptually splits into [0, index-1] (fixed) and [index, n-1] (to permute)
Swap pairs: Each transformation is a swap; restoration is simply swapping back

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
55
56
57
58
59
60
61
62
63
64
65
66
67
function permuteBySwapping<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const arr = [...elements]; // Work on a copy
    const n = arr.length;
    
    function backtrack(fixedUpTo: number): void {
        // Base case: all positions fixed
        if (fixedUpTo === n) {
            results.push([...arr]);
            return;
        }
        
        // Try each element from 'fixedUpTo' onwards in position 'fixedUpTo'
        for (let i = fixedUpTo; i < n; i++) {
            // SWAP: Move element at i to position fixedUpTo
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
            
            // RECURSE: Fix this position and permute the rest
            backtrack(fixedUpTo + 1);
            
            // UNSWAP: Restore original positions
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
        }
    }
    
    backtrack(0);
    return results;
}
 
// Visualize the swap mechanics
function permuteSwapVisualization<T>(elements: T[]): void {
    const arr = [...elements];
    const n = arr.length;
    let permCount = 0;
    
    function backtrack(fixedUpTo: number, depth: number): void {
        const indent = "  ".repeat(depth);
        console.log(`${indent}fixedUpTo=${fixedUpTo}, arr=[${arr}]`);
        
        if (fixedUpTo === n) {
            permCount++;
            console.log(`${indent}→ PERMUTATION #${permCount}: [${arr}]`);
            return;
        }
        
        for (let i = fixedUpTo; i < n; i++) {
            if (i !== fixedUpTo) {
                console.log(`${indent}Swap positions ${fixedUpTo} ↔ ${i}: ${arr[fixedUpTo]} ↔ ${arr[i]}`);
            } else {
                console.log(`${indent}Keep position ${fixedUpTo} as ${arr[fixedUpTo]}`);
            }
            
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
            backtrack(fixedUpTo + 1, depth + 1);
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
            
            if (i !== fixedUpTo) {
                console.log(`${indent}Unswap: restored to [${arr}]`);
            }
        }
    }
    
    backtrack(0, 0);
}
 
console.log("Swap-based permutation of [1, 2, 3]:");
permuteSwapVisualization([1, 2, 3]);

Understanding the Invariant:

At recursion level fixedUpTo:

Positions [0, fixedUpTo - 1] are fixed for this branch of exploration
Positions [fixedUpTo, n - 1] contain the remaining elements to arrange
Importantly, the elements in [fixedUpTo, n-1] are exactly those not fixed—just potentially reordered

The swapping maintains that all original elements are always present in the array; we're just shuffling their positions. This is why no 'used' tracking is needed—position itself encodes availability.

The Self-Swap Case:

When i === fixedUpTo, we 'swap' an element with itself—a no-op. This case represents choosing to keep the current element in its position. We must include this case to generate all permutations; skipping it would miss permutations where an element stays in its original position.

Invariants of the Swapping Approach

•Conservation: arr always contains exactly the original elements (in some order)
•Partition: arr[0..fixedUpTo-1] are fixed; arr[fixedUpTo..n-1] are free to permute
•Element Location: Each element is either in the fixed or free region, never both
•Restoration: After recursion returns, array is restored to pre-swap state
•Completeness: At base case, arr[0..n-1] is entirely fixed, representing one permutation

Head-to-Head Comparison

Let's systematically compare the two approaches across multiple dimensions. Understanding these tradeoffs enables informed algorithm selection.

Comprehensive Comparison: Inserting vs Swapping Approaches
Dimension	Inserting (Building)	Swapping (Rearranging)
Memory Overhead	O(n) for used array + O(n) for current array	O(1) extra (operates on input copy)
Modifications to Input	None (reads only)	Modifies array (requires copy or restoration)
Lexicographic Order	✅ Natural with sorted input	❌ Does not produce lex order
Conceptual Simplicity	Slightly clearer: 'pick unused elements'	Elegant but swap logic can confuse
Recursion Depth	O(n) - one level per position	O(n) - one level per position
Operations per Recursion	O(n) loop iterations	O(n-depth) loop iterations
Extension to Constraints	Easy: add conditions before selecting	Harder: constraints may not align with swaps
Multi-Threaded Safety	Safer: uses separate current array	Requires care: shared array state
Works for Non-Arrays	Yes: can work with any collection	Best suited for arrays/indexable structures
Per-Permutation Copy Cost	O(n) to copy current	O(n) to copy arr (same)

Detailed Analysis:

Memory Usage: The inserting approach uses O(n) extra for the used array and O(n) for current. The swapping approach needs no auxiliary structures but typically copies the input (O(n)) to avoid mutating the original. Net difference is minor—O(n) in both cases.

Lexicographic Ordering: This is one of the most significant practical differences. The inserting approach with sorted input produces lexicographically ordered output because we try smaller elements first at each position. The swapping approach does not: swapping disrupts suffix order.

For example, with input [1, 2, 3]:

Inserting: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ✓ Lexicographic
Swapping: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2] ✗ [3,2,1] before [3,1,2]

Adaptability to Constraints: When generating constrained permutations (e.g., no two consecutive elements can be the same category), checking constraints is more natural in the inserting approach—you check before pushing to current. With swapping, you'd check after swapping, which is slightly less intuitive.

When to Choose Inserting

•Lexicographic order required
•Need to apply complex constraints during generation
•Working with non-indexable collections
•Clarity of code is paramount
•Need to count elements chosen vs remaining

When to Choose Swapping

•Just need all permutations (order doesn't matter)
•Minimal memory overhead is critical
•Problem naturally involves swapping (anagrams, shuffles)
•Implementing Heap's Algorithm for optimal swap count
•Array mutation is acceptable/desired

Heap's Algorithm: The Optimal Swap Sequence

While our basic swapping approach works correctly, it's not optimal in terms of the number of swaps performed. Heap's Algorithm, discovered by B. R. Heap in 1963, generates all permutations such that each consecutive pair differs by exactly one swap.

Why This Matters:

Each swap is an O(1) operation, but it still has a cost. In the naive swapping approach, we swap and then swap back (restoration). Heap's Algorithm achieves a remarkable property: the minimal-change sequence. Each permutation is produced from the previous by the absolute minimum modification—a single swap, with no restoration swaps needed between permutations.

The Algorithm:

Heap's Algorithm uses a clever pattern based on array size parity:

If the current sub-array size is odd, always swap the first element with the last
If even, swap the current iteration index element with the last

This sounds cryptic but produces the optimal sequence.

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
55
56
57
58
59
60
61
62
function heapsAlgorithmRecursive<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const arr = [...elements];
    const n = arr.length;
    
    function generate(size: number): void {
        // Base case: only one element to arrange
        if (size === 1) {
            results.push([...arr]);
            return;
        }
        
        generate(size - 1);
        
        for (let i = 0; i < size - 1; i++) {
            // Swap based on parity of size
            if (size % 2 === 0) {
                // Even: swap element at index i with last element of sub-array
                [arr[i], arr[size - 1]] = [arr[size - 1], arr[i]];
            } else {
                // Odd: swap first element with last element of sub-array
                [arr[0], arr[size - 1]] = [arr[size - 1], arr[0]];
            }
            
            generate(size - 1);
        }
    }
    
    generate(n);
    return results;
}
 
// Demonstrate the minimal-change property
function showMinimalChanges<T>(elements: T[]): void {
    const perms = heapsAlgorithmRecursive(elements);
    
    console.log("Heap's Algorithm sequence:");
    for (let i = 0; i < perms.length; i++) {
        if (i === 0) {
            console.log(`#${i + 1}: [${perms[i]}]`);
        } else {
            // Find the swap
            const prev = perms[i - 1];
            const curr = perms[i];
            const diffs: number[] = [];
            for (let j = 0; j < curr.length; j++) {
                if (prev[j] !== curr[j]) diffs.push(j);
            }
            console.log(`#${i + 1}: [${curr}] ← swapped positions ${diffs[0]} ↔ ${diffs[1]}`);
        }
    }
}
 
showMinimalChanges([1, 2, 3]);
 
// Output:
// #1: [1,2,3]
// #2: [2,1,3] ← swapped positions 0 ↔ 1
// #3: [3,1,2] ← swapped positions 0 ↔ 2
// #4: [1,3,2] ← swapped positions 0 ↔ 1
// #5: [2,3,1] ← swapped positions 0 ↔ 2
// #6: [3,2,1] ← swapped positions 0 ↔ 1

Why Minimal-Change Sequences Matter

Minimal-change permutation sequences have applications beyond raw efficiency:

• Gray Codes for Permutations: Like binary Gray codes, useful in certain encoding schemes • Hamiltonian Paths: The permutation graph has Hamiltonian paths; Heap's Algorithm traces one • Testing: To test all permutations, minimal changes reduce setup between test cases • Animation: Visualizing permutations with smooth single-element transitions

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 heapsAlgorithmIterative<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const arr = [...elements];
    const n = arr.length;
    
    // Counter array for controlling the iteration
    const c: number[] = new Array(n).fill(0);
    
    // First permutation
    results.push([...arr]);
    
    let i = 0;
    while (i < n) {
        if (c[i] < i) {
            // Swap based on parity of i
            if (i % 2 === 0) {
                [arr[0], arr[i]] = [arr[i], arr[0]];
            } else {
                [arr[c[i]], arr[i]] = [arr[i], arr[c[i]]];
            }
            
            // Record this permutation
            results.push([...arr]);
            
            // Increment counter for this level
            c[i]++;
            
            // Reset to the start
            i = 0;
        } else {
            // Reset counter and move to next level
            c[i] = 0;
            i++;
        }
    }
    
    return results;
}
 
// Verify both versions produce same results
console.log("Recursive:", heapsAlgorithmRecursive([1,2,3]).length, "permutations");
console.log("Iterative:", heapsAlgorithmIterative([1,2,3]).length, "permutations");
 
// Show the iterative version's output
console.log("
Iterative Heap's for [A,B,C]:");
heapsAlgorithmIterative(["A", "B", "C"]).forEach((p, i) => {
    console.log(`${i + 1}: ${p.join("")}`);
});

Complexity of Heap's Algorithm:

Time: O(n!) for generating all permutations—optimal since we must produce n! outputs
Space: O(n) for the counter array in the iterative version; O(n) stack depth in recursive
Swaps: Exactly n! - 1 swaps total (one between each consecutive permutation)—optimal
Per-Permutation Overhead: O(1) amortized for the swap; O(n) for copying to results

Compared to the naive swapping approach which performs swap-recurse-unswap sequences, Heap's Algorithm is theoretically about twice as fast in terms of swap operations.

Steinhaus-Johnson-Trotter Algorithm

Another minimal-change permutation algorithm is the Steinhaus-Johnson-Trotter (SJT) algorithm, which has an elegant property: it generates permutations by always swapping adjacent elements. While Heap's Algorithm performs minimal swaps, the swapped elements might be far apart. SJT guarantees adjacency.

Conceptual Model:

Each element has an associated 'direction' (left or right). Elements 'move' in their direction by swapping with neighbors. When an element can't move further (blocked by the array boundary or a larger element), it becomes immobile and reverses direction. The largest mobile element always moves.

The Algorithm:

Start with elements in ascending order, all pointing left
Find the largest 'mobile' element (one that can swap in its direction)
Swap it in its direction
Reverse the direction of all elements larger than the one that moved
Record the permutation; repeat until no mobile element exists

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
interface DirectedElement<T> {
    value: T;
    direction: -1 | 1; // -1 = left, 1 = right
}
 
function steinhausJohnsonTrotter<T>(elements: T[]): T[][] {
    const n = elements.length;
    if (n === 0) return [[]];
    
    const results: T[][] = [];
    
    // Initialize with sorted elements, all pointing left
    const sorted = [...elements].sort((a, b) => 
        (a as unknown as number) - (b as unknown as number)
    );
    
    const arr: DirectedElement<T>[] = sorted.map(value => ({
        value,
        direction: -1 // All start pointing left
    }));
    
    // Helper: Find index of an element by value
    function findIndex(value: T): number {
        return arr.findIndex(el => el.value === value);
    }
    
    // Helper: Check if an element is mobile
    function isMobile(index: number): boolean {
        const el = arr[index];
        const targetIdx = index + el.direction;
        
        // Can't move out of bounds
        if (targetIdx < 0 || targetIdx >= n) return false;
        
        // Can't move past larger element
        return arr[targetIdx].value < el.value;
    }
    
    // Helper: Find largest mobile element
    function findLargestMobile(): number {
        let largestIdx = -1;
        let largestValue: T | undefined;
        
        for (let i = 0; i < n; i++) {
            if (isMobile(i)) {
                if (largestIdx === -1 || arr[i].value > largestValue!) {
                    largestIdx = i;
                    largestValue = arr[i].value;
                }
            }
        }
        
        return largestIdx;
    }
    
    // Record initial permutation
    results.push(arr.map(el => el.value));
    
    let mobileIdx = findLargestMobile();
    while (mobileIdx !== -1) {
        const mobileEl = arr[mobileIdx];
        const targetIdx = mobileIdx + mobileEl.direction;
        
        // Swap with adjacent in direction
        [arr[mobileIdx], arr[targetIdx]] = [arr[targetIdx], arr[mobileIdx]];
        
        // Reverse direction of all elements larger than the moved one
        for (const el of arr) {
            if (el.value > mobileEl.value) {
                el.direction *= -1;
            }
        }
        
        // Record this permutation
        results.push(arr.map(el => el.value));
        
        // Find next largest mobile
        mobileIdx = findLargestMobile();
    }
    
    return results;
}
 
// Demonstrate adjacent swaps
console.log("Steinhaus-Johnson-Trotter for [1, 2, 3]:");
const sjtPerms = steinhausJohnsonTrotter([1, 2, 3]);
sjtPerms.forEach((p, i) => {
    console.log(`#${i + 1}: [${p.join(", ")}]`);
});
 
// Verify adjacent-swap property
console.log("
Verifying adjacent swaps:");
for (let i = 1; i < sjtPerms.length; i++) {
    const prev = sjtPerms[i - 1];
    const curr = sjtPerms[i];
    const diffs: number[] = [];
    for (let j = 0; j < curr.length; j++) {
        if (prev[j] !== curr[j]) diffs.push(j);
    }
    const adjacent = Math.abs(diffs[0] - diffs[1]) === 1;
    console.log(`Swap ${diffs[0]} ↔ ${diffs[1]}: ${adjacent ? "✓ Adjacent" : "✗ NOT Adjacent"}`);
}

Practical Applications of Adjacent Transpositions

The adjacent-swap property of SJT is valuable when:

• Swapping non-adjacent elements is expensive (e.g., physical objects) • Analyzing permutation structure (transposition distance) • Generating permutations for certain proofs about the symmetric group • Creating smooth visual animations of all arrangements

Complexity:

Time: O(n × n!) — finding the largest mobile element takes O(n) each time
Space: O(n) for the direction array
Swaps: n! - 1, all adjacent

Comparison with Heap's Algorithm:

Heap's Algorithm is faster (O(n!) vs O(n × n!)) because it doesn't search for the mobile element—it follows a predetermined pattern. SJT's advantage is specifically the adjacent-swap guarantee, which Heap's doesn't provide.

Practical Algorithm Selection Guide

Given the variety of approaches, how do you choose? Here's a decision framework based on requirements:

Algorithm Selection Matrix
Requirement	Best Choice	Reason
Lexicographic output order	Inserting (with sorted input)	Natural ordering by selecting smallest first
Minimum memory	Basic Swapping	No auxiliary arrays beyond input copy
Minimum swaps	Heap's Algorithm	Exactly n!-1 swaps, no restorations
Adjacent swaps only	Steinhaus-Johnson-Trotter	Designed for this property
Easy to add constraints	Inserting	Check constraints before adding to current
Non-array input	Inserting	Works with any indexable collection
Maximum code clarity	Inserting	'Pick unused' is very intuitive
Iterative (no recursion)	Heap's Iterative or SJT	Both have iterative forms
Early termination	Inserting with Generator	Yield and break pattern fits naturally

Default Recommendation:

For most practical purposes, use the inserting (used array) approach:

It's conceptually clearer
It naturally produces lexicographic order
It's easier to extend for constraints
Memory overhead is negligible for typical problem sizes
It's what most developers expect and understand

Reserve Heap's Algorithm for performance-critical applications where you need pure generation speed and don't care about output order. Use SJT when adjacent swaps are specifically required.

Special Considerations:

Edge Cases and Gotchas

•Empty Input: All algorithms should handle n=0 by returning [[]] (one empty permutation) or skipping
•Single Element: Should return [[element]] — trivial but verify it
•Duplicates: Both basic approaches produce duplicates; need special handling (next page)
•Large n: For n > ~10, consider whether full enumeration is necessary; even optimal algorithms face factorial explosion
•Mutation Concerns: If input array must remain unchanged, always copy first (especially for swapping)
•Thread Safety: Swapping approach with shared state is not thread-safe without synchronization

Advanced Variations and Extensions

Both fundamental approaches extend to handle various specialized requirements. Here are some important variations:

K-Permutations:

Generating all arrangements of k elements from n (P(n,k)). Both approaches adapt easily:

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
55
56
57
58
// Inserting approach: stop when k elements selected
function kPermutationsInserting<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function backtrack(): void {
        if (current.length === k) {  // Modified: stop at k, not n
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Swapping approach: record when first k positions are fixed
function kPermutationsSwapping<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    const arr = [...elements];
    const n = arr.length;
    
    function backtrack(fixedUpTo: number): void {
        if (fixedUpTo === k) {  // Modified: stop at k, not n
            results.push(arr.slice(0, k));  // Only first k elements
            return;
        }
        
        for (let i = fixedUpTo; i < n; i++) {
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
            backtrack(fixedUpTo + 1);
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
        }
    }
    
    backtrack(0);
    return results;
}
 
console.log("3-permutations of [1,2,3,4] via inserting:");
console.log(kPermutationsInserting([1,2,3,4], 3).length, "permutations");
// Should be P(4,3) = 4×3×2 = 24
 
console.log("
2-permutations of [A,B,C] via swapping:");
kPermutationsSwapping(["A","B","C"], 2).forEach(p => console.log(p.join("")));
// Should be AB, AC, BA, BC, CA, CB (6 = 3×2)

Circular Permutations:

In circular arrangements, rotations are considered identical (e.g., ABC, BCA, CAB are the same necklace). The count reduces from n! to (n-1)!. Implementation: fix one element and permute the rest.

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
function circularPermutations<T>(elements: T[]): T[][] {
    if (elements.length <= 1) return [[...elements]];
    
    const results: T[][] = [];
    
    // Fix the first element
    const fixed = elements[0];
    const remaining = elements.slice(1);
    
    // Permute the remaining elements
    const used: boolean[] = new Array(remaining.length).fill(false);
    const current: T[] = [fixed]; // Start with fixed element
    
    function backtrack(): void {
        if (current.length === elements.length) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(remaining[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
console.log("Circular permutations of [1,2,3,4]:");
console.log("Count:", circularPermutations([1,2,3,4]).length, "(should be 3! = 6)");
circularPermutations([1,2,3]).forEach(p => console.log(p.join("-")));

Constrained Permutations:

Often we need permutations satisfying specific constraints. The inserting approach handles this most naturally:

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
// Example: Permutations where no two adjacent elements differ by 1
function constrainedPermutations(n: number): number[][] {
    const elements = Array.from({ length: n }, (_, i) => i + 1);
    const results: number[][] = [];
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function isValid(): boolean {
        if (current.length < 2) return true;
        const last = current[current.length - 1];
        const secondLast = current[current.length - 2];
        return Math.abs(last - secondLast) !== 1;
    }
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            // Tentatively add
            current.push(elements[i]);
            
            // Check constraint BEFORE recursing
            if (isValid()) {
                used[i] = true;
                backtrack();
                used[i] = false;
            }
            
            current.pop();
        }
    }
    
    backtrack();
    return results;
}
 
console.log("Permutations of [1,2,3,4] with no adjacent differing by 1:");
const constrained = constrainedPermutations(4);
console.log(`Found ${constrained.length} valid permutations (out of 24)`);
constrained.forEach(p => console.log(p.join(",")));
// Example valid: [2,4,1,3] - differences are 2,3,2, none equal to 1

Summary and Key Insights

We've conducted an exhaustive comparison of the inserting and swapping paradigms for permutation generation. Here are the essential takeaways:

Two Fundamental Paradigms:

Inserting (Building): Construct permutations by selecting unused elements into a growing sequence. Uses 'used' tracking. Produces lexicographic order with sorted input. Most versatile for constraints.
Swapping (Rearranging): Generate permutations by swapping elements within the array. No auxiliary tracking needed. Doesn't preserve lexicographic order. More efficient in swap count with optimizations.

Advanced Algorithms:

Heap's Algorithm: Minimal-change permutation generation with n!-1 total swaps (optimal). Non-adjacent swaps. Both recursive and elegant iterative forms.
Steinhaus-Johnson-Trotter: Minimal-change with adjacent-only swaps. Slightly slower but guarantees adjacency property.

Key Takeaways

•Choose inserting as default — clearer, lexicographic order, easy constraints
•Use Heap's for raw speed — when output order doesn't matter and performance is critical
•Swapping naturally maintains element conservation — the array always contains all original elements
•Both have O(n × n!) total time — we must generate n! outputs, each of size n
•Extensions follow the same patterns — k-permutations, circular, constrained all adapt naturally
•Know both approaches — different problems and constraints favor different algorithms

What's Next:

The next page addresses a critical practical issue: handling duplicate elements. When the input contains repeated values (e.g., [1, 1, 2]), naive algorithms produce duplicate permutations. We'll explore elegant techniques to generate only distinct permutations without inefficient post-processing.

Page Complete

You now possess deep knowledge of both fundamental permutation generation paradigms, their optimal variants (Heap's and SJT), and clear decision criteria for algorithm selection. This understanding enables you to choose and adapt algorithms confidently for any permutation generation scenario.

Swapping vs Inserting Approaches

Two Philosophies of Arrangement

What You Will Master

By the end of this page, you will understand:

The Inserting (Building) Approach

Conceptual Model:

Imagine arranging books on a shelf, one at a time:

Start with an empty shelf (empty partial permutation)
Pick any book from the pile (select an unused element)
Place it in the next available position on the shelf (append to partial permutation)
Repeat until all books are placed (all elements used)
Record the arrangement, then try alternative book orderings (backtrack)

Key Characteristics:

Separation: The source (input) and destination (current permutation) are distinct structures
Tracking: An auxiliary mechanism tracks which elements have been used
Growth: The partial permutation grows from length 0 to length n
Order Preservation: Elements maintain their relative positions in the output based on selection sequence

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
function permuteByInserting<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    
    // Track which elements have been used
    const used: boolean[] = new Array(n).fill(false);
    
    // Build the permutation element by element
    const current: T[] = [];
    
    function backtrack(): void {
        // Base case: all elements placed
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        // Try each unused element in the current position
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            // SELECT: Mark element as used and add to permutation
            used[i] = true;
            current.push(elements[i]);
            
            // RECURSE: Fill remaining positions
            backtrack();
            
            // DESELECT: Restore availability and remove from permutation
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Visualize the decision tree
function permuteWithVisualization<T>(elements: T[]): void {
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    let callCount = 0;
    
    function backtrack(depth: number): void {
        callCount++;
        const indent = "  ".repeat(depth);
        const usedStr = used.map((u, i) => u ? elements[i] : "_").join(",");
        
        console.log(`${indent}Call #${callCount}: current=[${current}], used={${usedStr}}`);
        
        if (current.length === n) {
            console.log(`${indent}→ FOUND: [${current}]`);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            console.log(`${indent}Trying element ${elements[i]} at position ${current.length}`);
            used[i] = true;
            current.push(elements[i]);
            
            backtrack(depth + 1);
            
            current.pop();
            used[i] = false;
            console.log(`${indent}Backtracked from ${elements[i]}`);
        }
    }
    
    backtrack(0);
    console.log(`
Total recursive calls: ${callCount}`);
}
 
console.log("Permutations of [A, B, C] with visualization:");
permuteWithVisualization(["A", "B", "C"]);

Invariants of the Inserting Approach

•Element Coverage: used[i] = true ⟺ elements[i] ∈ current
•Progress: |current| = depth of recursion = number of true values in used
•Distinctness: All elements in current are distinct (enforced by used check)
•Completeness: At depth n, current contains exactly the n elements, each once
•Order: Elements appear in current in the order they were selected (not necessarily original order)

Lexicographic Order Property

The Swapping (Rearranging) Approach

Conceptual Model:

Imagine shuffling numbered cards on a table:

Cards start in their original positions
For position 0, try swapping with every card from positions 0 to n-1
After each swap, fix position 0 and recursively permute positions 1 to n-1
After exploring, swap back to restore for the next trial
When all positions are fixed (base case), record the arrangement

Key Characteristics:

In-place: Operations modify the single array (or a copy thereof)
No auxiliary tracking: Position naturally encodes 'used vs remaining'
Partition: Array conceptually splits into [0, index-1] (fixed) and [index, n-1] (to permute)
Swap pairs: Each transformation is a swap; restoration is simply swapping back

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
55
56
57
58
59
60
61
62
63
64
65
66
67
function permuteBySwapping<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const arr = [...elements]; // Work on a copy
    const n = arr.length;
    
    function backtrack(fixedUpTo: number): void {
        // Base case: all positions fixed
        if (fixedUpTo === n) {
            results.push([...arr]);
            return;
        }
        
        // Try each element from 'fixedUpTo' onwards in position 'fixedUpTo'
        for (let i = fixedUpTo; i < n; i++) {
            // SWAP: Move element at i to position fixedUpTo
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
            
            // RECURSE: Fix this position and permute the rest
            backtrack(fixedUpTo + 1);
            
            // UNSWAP: Restore original positions
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
        }
    }
    
    backtrack(0);
    return results;
}
 
// Visualize the swap mechanics
function permuteSwapVisualization<T>(elements: T[]): void {
    const arr = [...elements];
    const n = arr.length;
    let permCount = 0;
    
    function backtrack(fixedUpTo: number, depth: number): void {
        const indent = "  ".repeat(depth);
        console.log(`${indent}fixedUpTo=${fixedUpTo}, arr=[${arr}]`);
        
        if (fixedUpTo === n) {
            permCount++;
            console.log(`${indent}→ PERMUTATION #${permCount}: [${arr}]`);
            return;
        }
        
        for (let i = fixedUpTo; i < n; i++) {
            if (i !== fixedUpTo) {
                console.log(`${indent}Swap positions ${fixedUpTo} ↔ ${i}: ${arr[fixedUpTo]} ↔ ${arr[i]}`);
            } else {
                console.log(`${indent}Keep position ${fixedUpTo} as ${arr[fixedUpTo]}`);
            }
            
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
            backtrack(fixedUpTo + 1, depth + 1);
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
            
            if (i !== fixedUpTo) {
                console.log(`${indent}Unswap: restored to [${arr}]`);
            }
        }
    }
    
    backtrack(0, 0);
}
 
console.log("Swap-based permutation of [1, 2, 3]:");
permuteSwapVisualization([1, 2, 3]);

Understanding the Invariant:

At recursion level fixedUpTo:

Positions [0, fixedUpTo - 1] are fixed for this branch of exploration
Positions [fixedUpTo, n - 1] contain the remaining elements to arrange
Importantly, the elements in [fixedUpTo, n-1] are exactly those not fixed—just potentially reordered

The Self-Swap Case:

Invariants of the Swapping Approach

•Conservation: arr always contains exactly the original elements (in some order)
•Partition: arr[0..fixedUpTo-1] are fixed; arr[fixedUpTo..n-1] are free to permute
•Element Location: Each element is either in the fixed or free region, never both
•Restoration: After recursion returns, array is restored to pre-swap state
•Completeness: At base case, arr[0..n-1] is entirely fixed, representing one permutation

Head-to-Head Comparison

Let's systematically compare the two approaches across multiple dimensions. Understanding these tradeoffs enables informed algorithm selection.

Comprehensive Comparison: Inserting vs Swapping Approaches
Dimension	Inserting (Building)	Swapping (Rearranging)
Memory Overhead	O(n) for used array + O(n) for current array	O(1) extra (operates on input copy)
Modifications to Input	None (reads only)	Modifies array (requires copy or restoration)
Lexicographic Order	✅ Natural with sorted input	❌ Does not produce lex order
Conceptual Simplicity	Slightly clearer: 'pick unused elements'	Elegant but swap logic can confuse
Recursion Depth	O(n) - one level per position	O(n) - one level per position
Operations per Recursion	O(n) loop iterations	O(n-depth) loop iterations
Extension to Constraints	Easy: add conditions before selecting	Harder: constraints may not align with swaps
Multi-Threaded Safety	Safer: uses separate current array	Requires care: shared array state
Works for Non-Arrays	Yes: can work with any collection	Best suited for arrays/indexable structures
Per-Permutation Copy Cost	O(n) to copy current	O(n) to copy arr (same)

Detailed Analysis:

For example, with input [1, 2, 3]:

Inserting: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ✓ Lexicographic
Swapping: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2] ✗ [3,2,1] before [3,1,2]

When to Choose Inserting

•Lexicographic order required
•Need to apply complex constraints during generation
•Working with non-indexable collections
•Clarity of code is paramount
•Need to count elements chosen vs remaining

When to Choose Swapping

•Just need all permutations (order doesn't matter)
•Minimal memory overhead is critical
•Problem naturally involves swapping (anagrams, shuffles)
•Implementing Heap's Algorithm for optimal swap count
•Array mutation is acceptable/desired

Heap's Algorithm: The Optimal Swap Sequence

Why This Matters:

The Algorithm:

Heap's Algorithm uses a clever pattern based on array size parity:

If the current sub-array size is odd, always swap the first element with the last
If even, swap the current iteration index element with the last

This sounds cryptic but produces the optimal sequence.

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
55
56
57
58
59
60
61
62
function heapsAlgorithmRecursive<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const arr = [...elements];
    const n = arr.length;
    
    function generate(size: number): void {
        // Base case: only one element to arrange
        if (size === 1) {
            results.push([...arr]);
            return;
        }
        
        generate(size - 1);
        
        for (let i = 0; i < size - 1; i++) {
            // Swap based on parity of size
            if (size % 2 === 0) {
                // Even: swap element at index i with last element of sub-array
                [arr[i], arr[size - 1]] = [arr[size - 1], arr[i]];
            } else {
                // Odd: swap first element with last element of sub-array
                [arr[0], arr[size - 1]] = [arr[size - 1], arr[0]];
            }
            
            generate(size - 1);
        }
    }
    
    generate(n);
    return results;
}
 
// Demonstrate the minimal-change property
function showMinimalChanges<T>(elements: T[]): void {
    const perms = heapsAlgorithmRecursive(elements);
    
    console.log("Heap's Algorithm sequence:");
    for (let i = 0; i < perms.length; i++) {
        if (i === 0) {
            console.log(`#${i + 1}: [${perms[i]}]`);
        } else {
            // Find the swap
            const prev = perms[i - 1];
            const curr = perms[i];
            const diffs: number[] = [];
            for (let j = 0; j < curr.length; j++) {
                if (prev[j] !== curr[j]) diffs.push(j);
            }
            console.log(`#${i + 1}: [${curr}] ← swapped positions ${diffs[0]} ↔ ${diffs[1]}`);
        }
    }
}
 
showMinimalChanges([1, 2, 3]);
 
// Output:
// #1: [1,2,3]
// #2: [2,1,3] ← swapped positions 0 ↔ 1
// #3: [3,1,2] ← swapped positions 0 ↔ 2
// #4: [1,3,2] ← swapped positions 0 ↔ 1
// #5: [2,3,1] ← swapped positions 0 ↔ 2
// #6: [3,2,1] ← swapped positions 0 ↔ 1

Why Minimal-Change Sequences Matter

Minimal-change permutation sequences have applications beyond raw efficiency:

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 heapsAlgorithmIterative<T>(elements: T[]): T[][] {
    const results: T[][] = [];
    const arr = [...elements];
    const n = arr.length;
    
    // Counter array for controlling the iteration
    const c: number[] = new Array(n).fill(0);
    
    // First permutation
    results.push([...arr]);
    
    let i = 0;
    while (i < n) {
        if (c[i] < i) {
            // Swap based on parity of i
            if (i % 2 === 0) {
                [arr[0], arr[i]] = [arr[i], arr[0]];
            } else {
                [arr[c[i]], arr[i]] = [arr[i], arr[c[i]]];
            }
            
            // Record this permutation
            results.push([...arr]);
            
            // Increment counter for this level
            c[i]++;
            
            // Reset to the start
            i = 0;
        } else {
            // Reset counter and move to next level
            c[i] = 0;
            i++;
        }
    }
    
    return results;
}
 
// Verify both versions produce same results
console.log("Recursive:", heapsAlgorithmRecursive([1,2,3]).length, "permutations");
console.log("Iterative:", heapsAlgorithmIterative([1,2,3]).length, "permutations");
 
// Show the iterative version's output
console.log("
Iterative Heap's for [A,B,C]:");
heapsAlgorithmIterative(["A", "B", "C"]).forEach((p, i) => {
    console.log(`${i + 1}: ${p.join("")}`);
});

Complexity of Heap's Algorithm:

Time: O(n!) for generating all permutations—optimal since we must produce n! outputs
Space: O(n) for the counter array in the iterative version; O(n) stack depth in recursive
Swaps: Exactly n! - 1 swaps total (one between each consecutive permutation)—optimal
Per-Permutation Overhead: O(1) amortized for the swap; O(n) for copying to results

Compared to the naive swapping approach which performs swap-recurse-unswap sequences, Heap's Algorithm is theoretically about twice as fast in terms of swap operations.

Steinhaus-Johnson-Trotter Algorithm

Conceptual Model:

The Algorithm:

Start with elements in ascending order, all pointing left
Find the largest 'mobile' element (one that can swap in its direction)
Swap it in its direction
Reverse the direction of all elements larger than the one that moved
Record the permutation; repeat until no mobile element exists

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
interface DirectedElement<T> {
    value: T;
    direction: -1 | 1; // -1 = left, 1 = right
}
 
function steinhausJohnsonTrotter<T>(elements: T[]): T[][] {
    const n = elements.length;
    if (n === 0) return [[]];
    
    const results: T[][] = [];
    
    // Initialize with sorted elements, all pointing left
    const sorted = [...elements].sort((a, b) => 
        (a as unknown as number) - (b as unknown as number)
    );
    
    const arr: DirectedElement<T>[] = sorted.map(value => ({
        value,
        direction: -1 // All start pointing left
    }));
    
    // Helper: Find index of an element by value
    function findIndex(value: T): number {
        return arr.findIndex(el => el.value === value);
    }
    
    // Helper: Check if an element is mobile
    function isMobile(index: number): boolean {
        const el = arr[index];
        const targetIdx = index + el.direction;
        
        // Can't move out of bounds
        if (targetIdx < 0 || targetIdx >= n) return false;
        
        // Can't move past larger element
        return arr[targetIdx].value < el.value;
    }
    
    // Helper: Find largest mobile element
    function findLargestMobile(): number {
        let largestIdx = -1;
        let largestValue: T | undefined;
        
        for (let i = 0; i < n; i++) {
            if (isMobile(i)) {
                if (largestIdx === -1 || arr[i].value > largestValue!) {
                    largestIdx = i;
                    largestValue = arr[i].value;
                }
            }
        }
        
        return largestIdx;
    }
    
    // Record initial permutation
    results.push(arr.map(el => el.value));
    
    let mobileIdx = findLargestMobile();
    while (mobileIdx !== -1) {
        const mobileEl = arr[mobileIdx];
        const targetIdx = mobileIdx + mobileEl.direction;
        
        // Swap with adjacent in direction
        [arr[mobileIdx], arr[targetIdx]] = [arr[targetIdx], arr[mobileIdx]];
        
        // Reverse direction of all elements larger than the moved one
        for (const el of arr) {
            if (el.value > mobileEl.value) {
                el.direction *= -1;
            }
        }
        
        // Record this permutation
        results.push(arr.map(el => el.value));
        
        // Find next largest mobile
        mobileIdx = findLargestMobile();
    }
    
    return results;
}
 
// Demonstrate adjacent swaps
console.log("Steinhaus-Johnson-Trotter for [1, 2, 3]:");
const sjtPerms = steinhausJohnsonTrotter([1, 2, 3]);
sjtPerms.forEach((p, i) => {
    console.log(`#${i + 1}: [${p.join(", ")}]`);
});
 
// Verify adjacent-swap property
console.log("
Verifying adjacent swaps:");
for (let i = 1; i < sjtPerms.length; i++) {
    const prev = sjtPerms[i - 1];
    const curr = sjtPerms[i];
    const diffs: number[] = [];
    for (let j = 0; j < curr.length; j++) {
        if (prev[j] !== curr[j]) diffs.push(j);
    }
    const adjacent = Math.abs(diffs[0] - diffs[1]) === 1;
    console.log(`Swap ${diffs[0]} ↔ ${diffs[1]}: ${adjacent ? "✓ Adjacent" : "✗ NOT Adjacent"}`);
}

Practical Applications of Adjacent Transpositions

The adjacent-swap property of SJT is valuable when:

Complexity:

Time: O(n × n!) — finding the largest mobile element takes O(n) each time
Space: O(n) for the direction array
Swaps: n! - 1, all adjacent

Comparison with Heap's Algorithm:

Practical Algorithm Selection Guide

Given the variety of approaches, how do you choose? Here's a decision framework based on requirements:

Algorithm Selection Matrix
Requirement	Best Choice	Reason
Lexicographic output order	Inserting (with sorted input)	Natural ordering by selecting smallest first
Minimum memory	Basic Swapping	No auxiliary arrays beyond input copy
Minimum swaps	Heap's Algorithm	Exactly n!-1 swaps, no restorations
Adjacent swaps only	Steinhaus-Johnson-Trotter	Designed for this property
Easy to add constraints	Inserting	Check constraints before adding to current
Non-array input	Inserting	Works with any indexable collection
Maximum code clarity	Inserting	'Pick unused' is very intuitive
Iterative (no recursion)	Heap's Iterative or SJT	Both have iterative forms
Early termination	Inserting with Generator	Yield and break pattern fits naturally

Default Recommendation:

For most practical purposes, use the inserting (used array) approach:

It's conceptually clearer
It naturally produces lexicographic order
It's easier to extend for constraints
Memory overhead is negligible for typical problem sizes
It's what most developers expect and understand

Reserve Heap's Algorithm for performance-critical applications where you need pure generation speed and don't care about output order. Use SJT when adjacent swaps are specifically required.

Special Considerations:

Edge Cases and Gotchas

•Empty Input: All algorithms should handle n=0 by returning [[]] (one empty permutation) or skipping
•Single Element: Should return [[element]] — trivial but verify it
•Duplicates: Both basic approaches produce duplicates; need special handling (next page)
•Large n: For n > ~10, consider whether full enumeration is necessary; even optimal algorithms face factorial explosion
•Mutation Concerns: If input array must remain unchanged, always copy first (especially for swapping)
•Thread Safety: Swapping approach with shared state is not thread-safe without synchronization

Advanced Variations and Extensions

Both fundamental approaches extend to handle various specialized requirements. Here are some important variations:

K-Permutations:

Generating all arrangements of k elements from n (P(n,k)). Both approaches adapt easily:

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
55
56
57
58
// Inserting approach: stop when k elements selected
function kPermutationsInserting<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function backtrack(): void {
        if (current.length === k) {  // Modified: stop at k, not n
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Swapping approach: record when first k positions are fixed
function kPermutationsSwapping<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    const arr = [...elements];
    const n = arr.length;
    
    function backtrack(fixedUpTo: number): void {
        if (fixedUpTo === k) {  // Modified: stop at k, not n
            results.push(arr.slice(0, k));  // Only first k elements
            return;
        }
        
        for (let i = fixedUpTo; i < n; i++) {
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
            backtrack(fixedUpTo + 1);
            [arr[fixedUpTo], arr[i]] = [arr[i], arr[fixedUpTo]];
        }
    }
    
    backtrack(0);
    return results;
}
 
console.log("3-permutations of [1,2,3,4] via inserting:");
console.log(kPermutationsInserting([1,2,3,4], 3).length, "permutations");
// Should be P(4,3) = 4×3×2 = 24
 
console.log("
2-permutations of [A,B,C] via swapping:");
kPermutationsSwapping(["A","B","C"], 2).forEach(p => console.log(p.join("")));
// Should be AB, AC, BA, BC, CA, CB (6 = 3×2)

Circular Permutations:

In circular arrangements, rotations are considered identical (e.g., ABC, BCA, CAB are the same necklace). The count reduces from n! to (n-1)!. Implementation: fix one element and permute the rest.

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
function circularPermutations<T>(elements: T[]): T[][] {
    if (elements.length <= 1) return [[...elements]];
    
    const results: T[][] = [];
    
    // Fix the first element
    const fixed = elements[0];
    const remaining = elements.slice(1);
    
    // Permute the remaining elements
    const used: boolean[] = new Array(remaining.length).fill(false);
    const current: T[] = [fixed]; // Start with fixed element
    
    function backtrack(): void {
        if (current.length === elements.length) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(remaining[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
console.log("Circular permutations of [1,2,3,4]:");
console.log("Count:", circularPermutations([1,2,3,4]).length, "(should be 3! = 6)");
circularPermutations([1,2,3]).forEach(p => console.log(p.join("-")));

Constrained Permutations:

Often we need permutations satisfying specific constraints. The inserting approach handles this most naturally:

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
// Example: Permutations where no two adjacent elements differ by 1
function constrainedPermutations(n: number): number[][] {
    const elements = Array.from({ length: n }, (_, i) => i + 1);
    const results: number[][] = [];
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function isValid(): boolean {
        if (current.length < 2) return true;
        const last = current[current.length - 1];
        const secondLast = current[current.length - 2];
        return Math.abs(last - secondLast) !== 1;
    }
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            // Tentatively add
            current.push(elements[i]);
            
            // Check constraint BEFORE recursing
            if (isValid()) {
                used[i] = true;
                backtrack();
                used[i] = false;
            }
            
            current.pop();
        }
    }
    
    backtrack();
    return results;
}
 
console.log("Permutations of [1,2,3,4] with no adjacent differing by 1:");
const constrained = constrainedPermutations(4);
console.log(`Found ${constrained.length} valid permutations (out of 24)`);
constrained.forEach(p => console.log(p.join(",")));
// Example valid: [2,4,1,3] - differences are 2,3,2, none equal to 1

Summary and Key Insights

We've conducted an exhaustive comparison of the inserting and swapping paradigms for permutation generation. Here are the essential takeaways:

Two Fundamental Paradigms:

Inserting (Building): Construct permutations by selecting unused elements into a growing sequence. Uses 'used' tracking. Produces lexicographic order with sorted input. Most versatile for constraints.
Swapping (Rearranging): Generate permutations by swapping elements within the array. No auxiliary tracking needed. Doesn't preserve lexicographic order. More efficient in swap count with optimizations.

Advanced Algorithms:

Heap's Algorithm: Minimal-change permutation generation with n!-1 total swaps (optimal). Non-adjacent swaps. Both recursive and elegant iterative forms.
Steinhaus-Johnson-Trotter: Minimal-change with adjacent-only swaps. Slightly slower but guarantees adjacency property.

Key Takeaways

•Choose inserting as default — clearer, lexicographic order, easy constraints
•Use Heap's for raw speed — when output order doesn't matter and performance is critical
•Swapping naturally maintains element conservation — the array always contains all original elements
•Both have O(n × n!) total time — we must generate n! outputs, each of size n
•Extensions follow the same patterns — k-permutations, circular, constrained all adapt naturally
•Know both approaches — different problems and constraints favor different algorithms

What's Next:

Page Complete