Heap’s Algorithm

Heap’s Algorithm is a classic algorithm used to generate all possible permutations of a finite sequence. It is particularly efficient for generating permutations and is widely used in combinatorial algorithms.

Overview

Heap’s Algorithm generates permutations by recursively swapping elements in the sequence. It is based on the idea of generating permutations by fixing the first element and recursively permuting the remaining elements.

Algorithm Steps

1. Initialization:

   • Start with a sequence of n elements.

2. Recursion:

   • If n = 1, output the permutation (base case).
   • Otherwise, for each element, swap it with the first element and recursively generate permutations of the remaining elements.
   • Restore the sequence by swapping back to maintain the original order.

3. Termination:

   • The recursion terminates when all permutations have been generated.

Time Complexity

The time complexity of Heap’s Algorithm is O(n!), where n is the number of elements. This is because the algorithm generates all possible permutations of the sequence.

JavaScript Implementation

Here is a JavaScript implementation of Heap’s Algorithm for generating permutations:

function heapsAlgorithm(n, array, result = []) {
  if (n === 1) {
    result.push(array.slice()); // Add a copy of the permutation
    return;
  }

  for (let i = 0; i < n - 1; i++) {
    heapsAlgorithm(n - 1, array, result);
    
    // Swap the elements based on the parity of n
    const j = n % 2 === 0 ? i : 0;
    [array[j], array[n - 1]] = [array[n - 1], array[j]];
  }

  // Generate permutations for the last element
  heapsAlgorithm(n - 1, array, result);
}

// Example usage
const array = [1, 2, 3];
const result = [];
heapsAlgorithm(array.length, array, result);
console.log(result); 
// Output: [ [ 1, 2, 3 ], [ 2, 1, 3 ], [ 3, 1, 2 ], [ 1, 3, 2 ], [ 2, 3, 1 ], [ 3, 2, 1 ] ]