algorithm - 证明堆算法生成排列

Question

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

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)!$ 排列，您可能需要解释每个元素都与其余元素的每个排列相邻。

如果您想通过示例查看解释，这篇博文提供了一个。