Iterating over permutations, part 2 – Heap’s algorithm

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

  1. 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
  2. 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
  3. Then set up a third loop inside the second one
  4. 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:

  1. At the end of the first iteration, swap the first element in the prefix into the controlled place
  2. At the end of the second iteration, swap the second element in the prefix into the controlled place
  3. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s