Heap’s Algorithm: An in-place permutation generator

In my research for an algorithm to generate the permutations of the elements of a finite set S of size n stored in an array and having an acceptable performance, I found the Heap’s Algorithm. This algorithm is O(n!), it uses the same array to perform the exchanges of pairs of elements (n! -1 swaps) to get all the different permutations.

The algorithm uses a design approach based on induction to get all the permutation of size n. This means that it assumes that the permutations of size (n-1) are already known and from them it builds the permutations of size n.

Implementation

Lets call our method heapGenerate(S, n, cb). Accordingly with the induction approach the algorithm has a base case:

  1. if n is equal to 1 then return cb(S)

where cb is a callback function that acts on the permutation, that is S itself for this case

Then it constructs each permutation after the generation of the permutations of size n-1:

2. else loop for each i from i=1 to n do

2.1 heapGenerate(S, n-1, cb)

2.2 if( n is even) then swap(i, n)

2.3 else swap(1, n)

Here is the implementation in JavaScript:

Time and Space Complexity Analysis:

We have two cases if n is equal to 1, it executes the callback (it doesn’t perform any swap so lets consider this a constant time c), in other case n> 1 it goes to the loop, for each i it calls generate(n-1) and makes a swap, this means it performs n(n-1)! -1 swaps that is n! -1 swaps, if any swap cost 3, well have 3(n! -1) this is O(n!).

And because all the swaps are in place and we store a couple of other variables the space we use is the size of the array S . Being still a recursive method it uses an n stack to do all the recursive calls.

Iterative implementation

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.