Heap’s algorithm wiki picture vs algorithm

Question

I’m trying to understand Heap’s algorithm from the Wikipedia page and I’m trying to compare the picture with the algorithm and I can’t seem to figure it out

this picture is from the wikipedia page

why would it switch the #1 and #2 first, shouldn’t it switch the #1 and #4 first?

I’m using java but this is just the code copied from Wikipedia, I understand that there is switching involved for the code in general

    if k = 1 then
        output(A)
    else
        // Generate permutations with kth unaltered
        // Initially k == length(A)
        generate(k - 1, A)

        // Generate permutations for kth swapped with each k-1 initial
        for i := 0; i < k-1; i += 1 do
            // Swap choice dependent on parity of k (even or odd)
            if k is even then
                swap(A[i], A[k-1]) // zero-indexed, the kth is at k-1
            else
                swap(A[0], A[k-1])
            end if
            generate(k - 1, A)

        end for
    end if

k is initially 4 so wouldn’t it switch A[0] and A[3] first?

Sorry in advance if this is a stupid question...

Tim Roberts · Accepted Answer · 2021-03-11 04:27:02Z

1

When k > 1, the very first thing it does is recurse. So, the calls go:

generate(4,A) calls
  generate(3,A) calls
    generate(2,A) calls
      generate(1,A) which prints A
      Now we do the processing for k==2.
      swap(0,1)
      generate(1,A) which prints the new A
      etc.

answered Mar 11, 2021 at 4:27

Tim Roberts

55.3k4 gold badges29 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

no lemon no melon Over a year ago

sorry if this is another stupid question, but what is generate(4,A), generate(3,A), generate(2,A), generate(1,A) then?

Tim Roberts Over a year ago

The original call is going to call generate(4,A), right? You have 4 things to swap, you're passing the array A. The first thing that generate is going to do is call generate(k-1,A). Since k is 4, that results in generate(3,A).

no lemon no melon Over a year ago

ok so that’s where the mysticalness comes from... they’re like dummivariables that keep track of everything, the mysticalness comes from how the algorithm is split up, and the generate(4,A), generate(3,A),generate(2,A),generate(1,A) appear to come out of nowhere... but really it’s a neat accounting trick with multiple moving parts

Tim Roberts Over a year ago

That's just how recursion works. That's the basis of the concept.

Collectives™ on Stack Overflow

Heap’s algorithm wiki picture vs algorithm

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related