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...

Answer 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.