I am trying to get an intuition for Heap's Algorithm which is used to generate permutations of a given set.

What I can't understand is why if n is even the letter swapped is i and when n is odd the letter shifted is at position 0.

I know it works but what is the intuition behind it ?

How come when n is odd there is always an unique letter in the beginning ? While if n is even the unique letters are from 0 to n-1 ?

The pseudo - code that I am looking at is -:

procedure generate(n : integer, A : array of any):
    if n = 1 then
        for i := 0; i < n - 1; i += 1 do
            generate(n - 1, A)
            if n is even then
                swap(A[i], A[n-1])
                swap(A[0], A[n-1])
            end if
        end for
        generate(n - 1, A)
    end if
  • 1
    $\begingroup$ Have you tried reading Heap's paper, a link to which appears on Wikipedia? Heap has this to say about the algorithm: That this scheme produces all possible permutations is obvious on inspection for the first few values of N. $\endgroup$ – Yuval Filmus Aug 3 '16 at 18:04
  • $\begingroup$ @YuvalFilmus I tried reading it, but I couldn't understand much. Can please elaborate on the line that you quoted ? $\endgroup$ – Kramer786 Aug 3 '16 at 18:49
  • 1
    $\begingroup$ It suggests that you explore the sequence of permutations generated by the algorithm, and then you might see why it works. In particular, it might be enough to understand the first and last permutations which are output during each call to generate(n–1, A). Code it and try it out for small $n$, and see if you can figure out a pattern. $\endgroup$ – Yuval Filmus Aug 3 '16 at 19:17
  • $\begingroup$ Would it be helpful if you think about Heap's algorithm as sorting network, which always exchanges elements leading to a cycle which is feeded a new element from swap, and the parity of elements dictates the place of swap? $\endgroup$ – Evil Aug 4 '16 at 6:17
  • $\begingroup$ I find the "is obvious on inspection" in the paper quite arrogant... $\endgroup$ – vonjd Apr 26 '19 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.