证明Heap算法生成排列

Question

我需要证明Heap算法的正确性，以生成排列。它的伪代码如下：

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]

（摘自Levitin的算法设计和分析介绍）

我知道我需要使用归纳来证明它的正确性，但我不确定如何去做。我已经证明了数学方程，但从未算过算法。

我认为证据看起来像这样......

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

我只是不确定如何完成诱导步骤。我甚至在这里正确的轨道？任何帮助将不胜感激。

Answer 1

1. 对于n = 1，heapPermute显然是正确的。打印{1}。
2. 假设heapPermute（）输出一组n！给定n的排列。然后
3. ??

现在，给出前两个假设，表明heapPermutate(n+1)返回所有（n + 1）！排列。

Answer 2

是的，这听起来像是一个好方法。想想如何递归地定义一组所有排列，即如何用{1..n}的排列来表达{1.. n-1}的排列。为此，回想一下有n!排列的归纳证据。归纳步骤如何进行？

Answer 3

一种递归方法绝对是可行的方法。鉴于您的前两个步骤，为了证明heapPermutate(n+1)返回所有$（n + 1）！$排列，您可能想要解释每个元素与其余元素的每个排列相邻。

如果您想通过示例查看解释，this blog post提供了一个。