I'm wanting to generate all possible permutations of the letters A - G (seven) and Heap's algorithm allegedly makes this possible.
However, when I look at the pseudo code from the Wikipedia page I see this:
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[0], A[n-1])
end if
end for
generate(n - 1, A)
end if
....and have no idea what it means.
So, I know that if I have seven letters (A-G) it'll apperently find all the possible permutations of the first six letters while the letter at the end stays the same.
Meaning, it'll find all possible permuations of A-F while G is on the end, and do that until each letter has been on the end.
Given, I have seven letters, that means "N" is odd, and thus I always switch the end letter (seventh one) with the letter that is in the first slot.
But (and I know this isn't how it works, but it's all I'm getting from it) won't that just result in the same two letters being swapped constantly and no diffent permutations?
I've scoured google results for the past 4 hours and can't find anything that explains line by line the above pseudo-code.
Help is greatly appreciated!!
generatebefore it does the swap, the letter inA[0]is not constant. Evidently, whennis odd, the letter atA[0]goes through all possibilities, whereas whennis even, you need to take the letter atA[i]to get all of the possibilities. Not sure how Heap proved that works for all values ofn.