Heap's algorithm for permutations

Question

I'm preparing for interviews and I'm trying to memorize Heap's algorithm:

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n; i += 1 do
            generate(n - 1, A)
            if n is even then
                swap(A[i], A[n-1])
            else
                swap(A[0], A[n-1])
            end if
        end for
    end if

This algorithm is a pretty famous one to generate permutations. It is concise and fast and goes hand-in-hand with the code to generate combinations.

The problem is: I don't like to memorize things by heart and I always try to keep the concepts to "deduce" the algorithm later.

This algorithm is really not intuitive and I can't find a way to explain how it works to myself.

Can someone please tell me why and how this algorithm works as expected when generating permutations?

Storage

I know this is old, but I've found a good explanation by Ruslan Ledesma-Garza on his site: ruslanledesma.com/2016/06/17/why-does-heap-work.html – Oidium

Answer 1

Heap's algorithm is probably not the answer to any reasonable interview question. There is a much more intuitive algorithm which will produce permutations in lexicographical order; although it is amortized O(1) (per permutation) instead of O(1), it is not noticeably slower in practice, and it is much easier to derive on the fly.

The lexicographic order algorithm is extremely simple to describe. Given some permutation, find the next one by:

1. Finding the rightmost element which is smaller than the element to its right.

2. Swap that element with the smallest element to its right which is larger than it.

3. Reverse the part of the permutation to the right of where that element was.

Both steps (1) and (3) are worst-case O(n), but it is easy to prove that the average time for those steps is O(1).

---

An indication of how tricky Heap's algorithm is (in the details) is that your expression of it is slightly wrong because it does one extra swap; the extra swap is a no-op if n is even, but significantly changes the order of permutations generated when n is odd. In either case, it does unnecessary work. See https://en.wikipedia.org/wiki/Heap%27s_algorithm for the correct algorithm (at least, it's correct today) or see the discussion at Heap's algorithm permutation generator

To see how Heap's algorithm works, you need to look at what a full iteration of the loop does to the vector, in both even and odd cases. Given a vector of even length, a full iteration of Heap's algorithm will rearrange the elements according to the rule

[1,...n] → [(n-2),(n-1),2,3,...,(n-3),n,1]

whereas if the vector is of odd length, it will be simply swap the first and last elements:

[1,...n] → [n,2,3,4,...,(n-2),(n-1),1]

You can prove that both of these facts are true using induction, although that doesn't provide any intuition as to why it's true. Looking at the diagram on the Wikipedia page might help.

Outlawry

The code given by the original poster is in fact correct. It is exactly the same as the code Sedgewick gave, see slide 13 at his presentation here: cs.princeton.edu/~rs/talks/perms.pdf – Sneer

@StephenFriedrich: I mention that slide in my answer to the linked question, #29043319 . The slide is incorrect (demonstrably so) but it also does not correspond to other discussions of the algorithm in Sedgewick's work. It's easy to make a mistake in a presentation (even if you're Robert Sedgewick); the papers I reference in that answer are more reliable. It's unfortunate that this particular presentation has not been corrected. – Outlawry

@connor: Good catch. Thanks. – Outlawry

@Outlawry Can you please explain why the lexicographic algorithm generates all permutations with these steps? I'm bad at math and am wondering how does doing those 3 steps gets you every arrangement of something intuitively... thanks – Inoffensive

@ima_prog: The lexicographic algorithm uses those three steps to find the next larger permutation (where larger is defined lexicographically). Lexicographic ordering is simply the way words are arranged in a dictionary, which many people wouldn't consider mathematics at all; if you don't understand how those steps find the next greater permutation, the simplest way of understanding is to just do the algorithm yourself with a pencil and a piece of paper. (Use a smallish vector or you'll need a very large piece of paper :-) Vectors with a lot of repeated values have fewer permutations, too.) – Outlawry

There's a general form for lexicographic generation of all kinds of sequences, and this is just one particularly simple application of that. (1) Scan backwards until you find an element which could be increased. (2) Increase it as little as possible. (3) Fill in the rest of the sequence using the smallest possible value at each point. In all cases, you need to know whether a given prefix could be the start of one of the sequences you're trying to create, and all the "possible values" in that description refer to possible values in one of these prefixes. – Outlawry

Again, the easiest way to understand is to do it with pencil and paper. At least, that's how I find my intuitions. – Outlawry

Answer 2

I found an article that tries to explain it here: Why does Heap's algorithm work?

However, I think it is hard to understand it, so came up with an explanation that is hopefully easier to understand:

---

Please just assume that these statements are true for a moment (i'll show that later):

Each invocation of the "generate" function

(I) where n is odd, leaves the elements in the exact same ordering when it is finished.

(II) where n is even, rotates the elements to the right, for example ABCD becomes DABC.

So in the "for i"-loop

when

• n is even

  The recursive call "generate(n - 1, A)" does not change the order.

  So the for-loop can iteratively swap the element at i=0..(n-1) with the element at (n - 1) and will have called "generate(n - 1, A)" each time with another element missing.

• n is odd

  The recursive call "generate(n - 1, A)" has rotated the elements right.

  So the element at index 0 will always be a different element automatically.

  Just swap the elements at 0 and (n-1) in each iteration to produce a unique set of elements.

---

Finally, let's see why the initial statements are true:

Rotate-right

(III) This series of swaps result in a rotation to the right by one position:

A[0] <-> A[n - 1]
A[1] <-> A[n - 1]
A[2] <-> A[n - 1]
...
A[n - 2] <-> A[n - 1]

For example try it with sequence ABCD:

A[0] <-> A[3]: DBCA
A[1] <-> A[3]: DACB
A[2] <-> A[3]: DABC

No-op

(IV) This series of steps leaves the sequence in the exact same ordering as before:

Repeat n times:
    Rotate the sub-sequence a[0...(n-2)] to the right
    Swap: a[0] <-> a[n - 1]

Intuitively, this is true:

If you have a sequence of length 5, then rotate it 5 times, it ends up unchanged.

Taking the element at 0 out before the rotation, then after the rotation swapping it with the new element at 0 does not change the outcome (if rotating n times).

Induction

Now we can see why (I) and (II) are true:

If n is 1: Trivially, the ordering is unchanged after invoking the function.

If n is 2: The recursive calls "generate(n - 1, A)" leave the ordering unchanged (because it invokes generate with first argument being 1). So we can just ignore those calls. The swaps that get executed in this invocation result in a right-rotation, see (III).

If n is 3: The recursive calls "generate(n - 1, A)" result in a right-rotation. So the total steps in this invocation equal (IV) => The sequence is unchanged.

Repeat for n = 4, 5, 6, ...

Sneer

Swap: a[0] <-> a[n] is clearly incorrect since there is no a[n]. If you change it to swapping a[0] with a[n-1], you introduce an additional swap, making the permutation sequence not a Gray code. (This was evident in the uncorrected Wikipedia page.) Although it is not a Gray code, it is still sequences through all permutations, so the error is easy to miss. – Outlawry

Thanks @Outlawry for catching that off-by-one error. Corrected. Yes, the code is doing a couple of swap operations that are unnecessary. I don't really see how that matters because the goal is to generate all permutations, which it does - unlike the current code in the Wikipedia article on Heaps's algorithm, which is just broken. Is there any "authoritative" description of Heap's algorithm? I couldn't decipher the structure diagram in the original article linked at Wikipedia: comjnl.oxfordjournals.org/content/6/3/293.full.pdf – Sneer

people keep on breaking the Wikipedia code, especially by using tbe erroneous prezzy but also by misreading the code. But the last time i looked at it, it worked fine. Both the original paper and the 1977 paper by sedgewick are correct and there is a copy of the code from sedgewick 1977 in my answer to the linked question. – Outlawry

Here is a quick translation of the Wikipedia code into C++, and its correct output for n==3 coliru.stacked-crooked.com/a/0c239cfc7b7f4d46 and n==4 coliru.stacked-crooked.com/a/0c239cfc7b7f4d46 Perhaps you would be so kind as to substantiate your claim that it is "just broken" or explain how my translation differs from the Wikipedia pseudocode. Otherwise, you have some retracting to do. – Outlawry

By contrast, here is the incorrect code from the OP, which you claimed in a comment to be correct. coliru.stacked-crooked.com/a/72c850885d09d4cb It does in fact generate all 24 permutations, but it goes from cbad to dbca at line 7, which is not a Gray code because it is not a swap of two elements. – Outlawry

Ok, thanks for the code. I officially retract my earlier statements! When I myself translated the pseudo code, I used kotlin and wrongly made the for statement "for(i in 0..(n - 1)) {" instead of "for(i in 0..(n - 2)) {". I wish however there was a language construct that made "return-in-the-middle-of-a-loop" more elegant (repeating parts of the loop after the loop is as inelegant as using "if" and "break" in the middle of a while(true)). – Sneer

Concerning swap counts: For 4-elements your version does 23 swaps, while the one with bogus swaps does 40 swaps. Here's the code in kotlin: try.kotlinlang.org/#/UserProjects/t527ems4u5gpd62atvqsc77glv/… – Sneer

Let us continue this discussion in chat. – Outlawry

Answer 3

The reason Heap’s algorithm constructs all permutations is that it adjoins each element to each permutation of the rest of the elements. When you execute Heap's algorithm, recursive calls on even length inputs place elements n, (n-1), 2, 3, 4, ..., (n-2), 1 in the last position and recursive calls on odd length inputs place elements n, (n-3), (n-4), (n-5), ..., 2, (n-2), (n-1), 1 in the last position. Thus, in either case, all elements are adjoined with all permutations of n - 1 elements.

If you would like a more detailed an graphical explanation, have a look at this article.

Nisus

Answer 4

function* permute<T>(array: T[], n = array.length): Generator<T[]> {
if (n > 1) {
    for (let ix = 1; ix < n; ix += 1) {
        for (let _arr of permute(array, n - 1)) yield _arr
        let j = n % 2 ? 0 : ix - 1
        ;[array[j], array[n - 1]] = [array[n - 1], array[j]]
    }
    for (let _arr of permute(array, n - 1)) yield _arr
} else yield array

}

Example use:

for (let arr of permute([1, 2, 3])) console.log(arr)

Faintheart

Answer 5

Trickiest part for me to understand as I am still studying it as well was the recursive expression:

for i := 0; i < n; i += 1 do
   generate(n - 1, A)

• I read it as evaluate at every i to n
• have the terminate condition at n = 1
• either an odd/even n return on execution

Since it calls and returns one 1 for every i as n is passed back recursively. Minimal change can be achieved when permuting every n + 1 passed back.

Richey

this recursive approach will be quite slow, specially for larger numbers, instead use iterative approach – Ambitendency

Answer 6

just a side tip. the heap algorithm will generate n! combinations. i.e if you pass n=[1,2,3] as a input the result will be n! which is

Happily

This is more appropriately posted as a comment rather than an answer. You can find more information on how to write good answers here: stackoverflow.com/help/how-to-answer – Imeldaimelida