Proving Heap's Algorithm for Generating Permutations

Question

I need to prove the correctness of Heap's algorithm for generating permutations. The pseudocode for it is as follows:

HeapPermute(n)
//Implements Heap’s algorithm for generating permutations
//Input: A positive integer n and a global array A[1..n]
//Output: All permutations of elements of A
if n = 1
   write A
else
   for i ←1 to n do
   HeapPermute(n − 1)
   if n is odd
      swap A[1] and A[n]
   else swap A[i] and A[n]

(taken from Introduction to the Design and Analysis of Algorithms by Levitin)

I know I need to use induction to prove its correctness, but I'm not sure exactly how to go about doing so. I've proved mathematical equations but never algorithms.

I was thinking the proof would look something like this...

1) For n = 1, heapPermute is obviously correct. {1} is printed. 
2) Assume heapPermute() outputs a set of n! permutations for a given n. Then 
??

I'm just not sure how to go about finishing the induction step. Am I even on the right track here? Any help would be greatly appreciated.

Answer 1

1. For n = 1, heapPermute is obviously correct. {1} is printed.
2. Assume heapPermute() outputs a set of n! permutations for a given n. Then
3. ??

Now, given the first two assumptions, show that heapPermutate(n+1) returns all the (n+1)! permutations.

Answer 2

Yes, that sounds like a good approach. Think about how to recursively define a set of all permutations, i.e. how can be permutations of {1..n} be expressed in terms of permutations of {1.. n-1}. For this, recall the inductive proof that there are n! permutations. How does the inductive step proceed there?

Answer 3

A recursive approach is definitely the way to go. Given your first two steps, to prove that heapPermutate(n+1) returns all the $(n+1)!$ permutations, you may want to explain that each element is adjoined to each permutation of the rest of the elements.

If you would like to have a look at an explanation by example, this blog post provides one.