Generating Combinatorial Objects $149$

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$]$

a$.$ Trace the algorithm by hand for n $=2,3,$ and $4.$

b$.$ Prove the correctness of Heap$$s algorithm.

c$.$ What is the time efficiency of HeapPermute?