Heap's Algorithm

What are Permutations?

A permutation is a rearrangement of elements in a set. For a set of n distinct elements, there are exactly n! (n factorial) possible permutations. For example, the set {A, B, C} has 3! = 6 permutations:

Generating all permutations is a fundamental problem in computer science, with applications ranging from cryptography to optimization algorithms. While there are many ways to generate permutations, Heap's algorithm stands out for its elegance and efficiency.

Understanding Heap's Algorithm

B. R. Heap discovered this algorithm in 1963. Its brilliance is deceptively simple: to generate all n! permutations, it swaps just two elements between each permutation. This creates a complete sequence where each arrangement differs from the previous by exactly one swap.

procedure generate(k : integer, A : array):
    if k = 1 then
        output(A)
    else
        // Generate permutations with kth element in each position
        generate(k - 1, A)
        
        for i := 0 to k - 2 do
            if k is even then
                swap(A[i], A[k-1])
            else
                swap(A[0], A[k-1])
            generate(k - 1, A)

The algorithm's clever trick is its swap pattern based on whether k (the current size) is even or odd:

• When k is even: Rotate through positions - swap k-1 with position 0, then 1, then 2, etc.
• When k is odd: Always swap k-1 with position 0 (the first element)

This pattern ensures every possible arrangement is generated exactly once, with minimal movement.

Interactive Visualization

Let's see Heap's algorithm in action. This visualization shows exactly how the algorithm generates all permutations by swapping just two elements at each step.

The Recursive Structure

Heap's algorithm works by recursively solving smaller problems. Think of it like this: to permute n elements, it first generates all permutations of n-1 elements, then systematically moves the nth element through different positions.

The tree below shows this recursive breakdown. Each node represents a recursive call with a specific k value (the size of the sub-problem). The leaf nodes (k=1) are where permutations are actually output:

Implementation Variations

While the recursive version is easiest to understand, Heap's algorithm can be implemented in several ways. Each approach has its own advantages:

function heapPermutation(array) {
    const result = [];
    
    function generate(k, arr) {
        if (k === 1) {
            result.push([...arr]);
            return;
        }
        
        generate(k - 1, arr);
        
        for (let i = 0; i < k - 1; i++) {
            if (k % 2 === 0) {
                [arr[i], arr[k - 1]] = [arr[k - 1], arr[i]];
            } else {
                [arr[0], arr[k - 1]] = [arr[k - 1], arr[0]];
            }
            generate(k - 1, arr);
        }
    }
    
    generate(array.length, array);
    return result;
}

function heapPermutationIterative(array) {
    const result = [];
    const c = new Array(array.length).fill(0);
    
    result.push([...array]);
    
    let i = 0;
    while (i < array.length) {
        if (c[i] < i) {
            if (i % 2 === 0) {
                [array[0], array[i]] = [array[i], array[0]];
            } else {
                [array[c[i]], array[i]] = [array[i], array[c[i]]];
            }
            result.push([...array]);
            c[i]++;
            i = 0;
        } else {
            c[i] = 0;
            i++;
        }
    }
    
    return result;
}

// Non-recursive, fixed O(n) space implementation
function heapPermutationFixedSpace(array, callback) {
    // Uses only O(n) auxiliary space via the counter array
    const n = array.length;
    const c = new Array(n).fill(0);
    
    // Process the initial permutation
    callback([...array]);
    
    // The algorithm uses a clever counting mechanism
    // c[i] counts how many times we've done the i-th swap
    let i = 0;
    while (i < n) {
        if (c[i] < i) {
            // Perform the swap based on parity
            if (i % 2 === 0) {
                [array[0], array[i]] = [array[i], array[0]];
            } else {
                [array[c[i]], array[i]] = [array[i], array[c[i]]];
            }
            
            // Process the new permutation
            callback([...array]);
            
            // Increment counter and reset position
            c[i]++;
            i = 0;
        } else {
            // Reset counter and move to next position
            c[i] = 0;
            i++;
        }
    }
}

// Example usage:
const arr = ['A', 'B', 'C', 'D'];
heapPermutationFixedSpace(arr, perm => {
    console.log(perm.join(''));
});

function* heapPermutationGenerator(array) {
    const c = new Array(array.length).fill(0);
    
    yield [...array];
    
    let i = 0;
    while (i < array.length) {
        if (c[i] < i) {
            if (i % 2 === 0) {
                [array[0], array[i]] = [array[i], array[0]];
            } else {
                [array[c[i]], array[i]] = [array[i], array[c[i]]];
            }
            yield [...array];
            c[i]++;
            i = 0;
        } else {
            c[i] = 0;
            i++;
        }
    }
}

The Fixed-Space Implementation

One of the most elegant aspects of Heap's algorithm is that it can be implemented non-recursively using only O(n) auxiliary space. This fixed-space version is particularly valuable for embedded systems or when dealing with very large permutations.

Performance Analysis

What makes Heap's algorithm special? It achieves the theoretical minimum number of swaps: exactly n! - 1 swaps to generate all n! permutations. That's just one swap between each consecutive permutation!

The chart above shows how different algorithms scale. Notice how Heap's algorithm maintains optimal performance even as the input size grows.

Real-World Applications

Heap's algorithm finds use in many practical scenarios:

Conclusion

Heap's algorithm exemplifies the beauty of computer science: a simple, elegant solution to a fundamental problem. Its minimal-swap property and straightforward implementation make it a go-to choice for permutation generation.

Understanding algorithms like Heap's helps us appreciate how clever insights can lead to optimal solutions. Whether you're solving puzzles, optimizing routes, or exploring combinatorial spaces, Heap's algorithm provides an efficient tool for generating all possible arrangements.