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