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

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