# Heap’s Algorithm

Find All the Permutations of a Set of Elements

A classic technical interview question is finding the permutations of characters in a string. This is a subset of a larger problem of finding all the permutations of elements in a set. One of the most common algorithms to tackle this problem is Heap’s Algorithm. Heap’s is a relatively young algorithm being first proposed by B. R. Heap in 1963.

I’ve laid out the algorithm's pseudocode with explanation below:

`PROCEDURE HEAP(S,N)`

IF n == 1 THEN

process S

ELSE

FOR i := 0 TO n - 1

Heap(S, n - 1)

IF n is even THEN

swap S[0] and S[n - 1]

ELSE

swap S[i] and S[n - 1]

END IF

END FOR

END IF

END PROCEDURE

First, in the base case, at the end of the recursion calls, the final permutation is added to a list or printed to a terminal. If the algorithm works correctly, all of the input’s various permutations will be outputted at this point.

The second branch of the conditional is called if the permutation has not met the bottom yet. In other words, N is between 2 and the maximum number — 1.

In this else block, a loop iterates from 0 to n -1. On each iteration, the algorithm makes a recursive call to Heap. Afterwards, two elements of the string swap based on whether n is even or odd.

The java code implementation for the algorithm is shown below.

`public List<String> findPermutations(String string) {`

findPermutationswithN(string, string.length());

return perms;

}

private void findPermutationswithN(String string, Integer size) {

if(size == 1) {

perms.add(string);

}

else {

for(Integer i = 0; i < size;i++) {

findPermutationswithN(string, size - 1);

if(size % 2 == 0) {

string = swap(string, 0, size - 1);

}

else {

string = swap(string, i, size - 1);

}

}

}

}

private String swap(String string,Integer i, Integer j) {

String[] stringarr = string.split("");

String temp = stringarr[i];

stringarr[i] = stringarr[j];

stringarr[j] = temp;

StringBuilder builder = new StringBuilder();

for(String s: stringarr) {

builder.append(s);

}

String str = builder.toString();

return str;

}

## Why does it work?

**Number of Cycles**

First of all, we know that the total number of permutations for a list of n elements will be n! factorial, where:

*n! = n*(n-1)*(n-2)...1*

Consequently, to produce the correct result, the algorithm must make n! — 1 swap with each swap creating a unique order of elements. Looking at the algorithm more closely, we can observe that through a combination of recursive calls and nested loops, the algorithm goes through (n) and then (n-1), etc.. calls on each iteration.

`FOR i := 0 TO n - 1`

Heap(S, n - 1)

IF n is even THEN

swap S[0] and S[n - 1]

ELSE

swap S[i] and S[n - 1]

END IF

END FOR

Zeroing in on the else block of code reveals the following:

- The algorithm makes n recursive calls from the first statement in the loop block.
- This recursion calls another nested for loop that initiates (n — 1) cycles as the n integer has been decremented.
- After the recursive call returns on each iteration of the loop, the algorithm calls an if-else block.
- The if-else block swaps elements based on the evenness or oddness of n.
- This process repeats until the integer reaches 1 and the permutation is added to the list or outputted.
- Putting it all together, the algorithm swaps n(n — 1)(n — 2) — 1… times as the very first permutation will skip the swap by missing the else block.

**Uniqueness**

The next pertinent question arises: Why does the algorithm produce unique permutations. To understand this, we need to think about how the algorithm works in terms of nesting. The recursive call to Heap is nested within an inner loop. This nested recursion then calls another nested inner loop. The cycle repeats until the integer reaches 1, and the final permutation is processed. Like a Russian nested doll, the algorithm uses self-similarity and, in the process, visits every possible permutation once. Let’s take a look at an example:

Examining the sequence, we can see that the last element is held constant as the algorithm moves through all the first three letters' permutations. Subdividing the problem further, we observe that the third letter is held constant while the remaining two letters are swapped and so on. In other words, Heap’s Algorithm applies a decrease and conquers method to visit each permutation sequentially. In this way, the algorithm visits each permutation once until all are found and processed. It accomplishes this with the application of nested recursive calls.

## Space and Time Complexity

Unfortunately, in computer science, combinatorial problems are almost always extremely inefficient. This is certainly true of Heap’s Algorithm. By necessity, the number of operations relative to the input must be factorial. This is simply the number of swaps made as the algorithm progresses. Consequently, the time complexity is O(n!).

The space complexity is significantly better. Our input is a string or list consisting of n elements. Given that the elements are swapped in place, the space complexity is O(n).

## Key Take-Aways

- Heap’s Algorithm generates all of the permutations of a list or string. B.R Heap created it in 1963.
- It uses a decrease and conquers method with recursion and looping to find every unique permutation of the input list or string.
- Heap’s Algorithm has a space and time complexity of O(n) and O(n!) respectively.