Last time we talked about how Nariyana Pandita iterated over permutations in India in the 1300s. Also see Iterating over permutations, part 3 – Steinhaus-Johnson-Trotter algorithm.

600 years later, in 1963, B. R. Heap showed a completely different way to do it. Heap’s algorithm (original paper, PDF) takes a divide-and-conquer approach. I have a PowerShell implementation of this too.

Example: A B C D E F G

- First set up an outer loop. This loop controls the last place in the permutation and cycles all of the elements through it in turn:
- ? ? ? ? ? ?
**G** - ? ? ? ? ? ?
**D** - ? ? ? ? ? ?
**C** - ? ? ? ? ? ?
**B** - ? ? ? ? ? ?
**E** - ? ? ? ? ? ?
**F** - ? ? ? ? ? ?
**A**

- ? ? ? ? ? ?
- Then set up a second loop inside the first one. This loop controls the next-to-last place in the permutation. Note that this loop iterates one fewer time than the outer loop.
- ? ? ? ? ?
**F**G - ? ? ? ? ?
**E**G - ? ? ? ? ?
**B**G - ? ? ? ? ?
**C**G - ? ? ? ? ?
**D**G - ? ? ? ? ?
**A**G

- ? ? ? ? ?
- Then set up a third loop inside the second one
- And fourth loop inside that
- …

… and so on until every place in the permutation has a loop. Have the innermost loop print the permutation or do what ever operation on it is desired.

All the loops work in the same way. Consider the loop that controls **the kth place** in the permutation. Call the preceding (

*k*– 1) places the

*prefix*.

Some examples:

*k*= 6:*A B C D E***F**G*k*= 5:*A B C D***E**F G

If the length of the prefix (*k* – 1) is *odd*, then the loop swaps elements as follows:

- At the end of the first iteration, swap the first element in the prefix into the controlled place
- At the end of the second iteration, swap the second element in the prefix into the controlled place
- …
- At the end of the (
*k*– 1)^{th}iteration, swap the (*k*– 1)^{th}element in the prefix into the controlled place

Note that every element in the prefix takes its turn in the controlled place.

If the length of the prefix (*k* – 1) is *even*, then the shuffling of the prefix by the inner loops is more fortuitous, and the loop’s swapping logic is simpler:

- At the end of
*every*iteration, swap the first element in the prefix into the controlled place

This is easier to see in action. Here are three loops *k* = 2, *k* = 3, and *k* = 4 working together:

*k*= 4, first iteration begins*A B C***D**E F G*k*= 3, first iteration begins*A B***C**D E F G*k*= 2, first iteration begins*A***B**C D E F G*k*= 2, swap the first and second elements, second iteration begins*B***A**C D E F G

*k*= 3, swap the first and third elements, second iteration begins*C A***B**D E F G*k*= 2, first iteration begins*C***A**B D E F G*k*= 2, swap the first and second elements, second iteration begins*A***C**B D E F G

*k*= 3, swap the*first*and third elements (again), third iteration begins*B C***A**D E F G*k*= 2, first iteration begins*B***C**A D E F G*k*= 2, swap the first and second elements, second iteration begins*C***B**A D E F G

*k*= 4 – swap the first and fourth elements, second iteration begins*D B A***C**E F G*k*= 3, first iteration begins*D B***A**C E F G*k*= 2, first iteration begins*D***B**A C E F G*k*= 2, swap the first and second elements, second iteration begins*B***D**A C E F G

*k*= 3, swap the first and third elements, second iteration begins*A D***B**C E F G*k*= 2, first iteration begins*A***D**B C E F G*k*= 2, swap the first and second elements, second iteration begins*D***A**B C E F G

*k*= 3, swap the*first*and third elements (again), third iteration begins*B A***D**C E F G*k*= 2, first iteration begins*B***A**D C E F G*k*= 2, swap the first and second elements, second iteration begins*A***B**D C E F G

*k*= 4 – swap the second and fourth elements, third iteration begins*A C D***B**E F G*k*= 3, first iteration begins*A C***D**B E F G*k*= 2, first iteration begins*A***C**D B E F G*k*= 2, swap the first and second elements, second iteration begins*C***A**D B E F G

*k*= 3, swap the first and third elements, second iteration begins*D A***C**B E F G*k*= 2, first iteration begins*D***A**C B E F G*k*= 2, swap the first and second elements, second iteration begins*A***D**C B E F G

*k*= 3, swap the*first*and third elements (again), third iteration begins*C D***A**B E F G*k*= 2, first iteration begins*C***D**A B E F G*k*= 2, swap the first and second elements, second iteration begins*D***C**A B E F G

*k*= 4 – swap the third and fourth element, fourth iteration begins*D C B***A**E F G*k*= 3, first iteration begins*D C***B**A E F G*k*= 2, first iteration begins*D***C**B A E F G*k*= 2, swap the first and second elements, second iteration begins*C***D**B A E F G

*k*= 3, swap the first and third elements, second iteration begins*B D***C**A E F G*k*= 2, first iteration begins*B***D**C A E F G*k*= 2, swap the first and second elements, second iteration begins*D***B**C A E F G

*k*= 3, swap the*first*and third elements (again), third iteration begins*C B***D**A E F G*k*= 2, first iteration begins*C***B**D A E F G*k*= 2, swap the first and second elements, second iteration begins*B***C**D A E F G

Note that the *k* = 4 loop, which has an odd-length prefix, swaps first and fourth, second and fourth, third and fourth; but the *k* = 3 loop, which has an even-length prefix, swaps first and third, *first* and third. The *k* = 3 loop has less work to do, because the *k* = 2 loop moved a new element to the first place for it.

## 2 thoughts on “Iterating over permutations, part 2 – Heap’s algorithm”