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 output(A) else for i := 0; i < n - 1; i += 1 do generate(n - 1, A) if n is even then swap(A[i], A[n-1]) else swap(A, A[n-1]) end if end for generate(n - 1, A) end if