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