1

順列を生成するヒープのアルゴリズムが正しいことを証明する必要があります。その擬似コードは次のとおりです。

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

誘導ステップを終了する方法がわかりません。私はここで正しい軌道に乗っていますか？どんな助けでも大歓迎です。

4

3 に答える 3

1
  1. n = 1 の場合、heapPermute は明らかに正しいです。{1} が出力されます。
  2. heapPermute() が n! のセットを出力するとします。与えられた n の順列。それで
  3. ??

ここで、最初の 2 つの仮定が与えられると、すべての(n+1)heapPermutate(n+1)が返されることを示します。順列。

于 2014-05-04T14:16:43.643 に答える
1

はい、それは良いアプローチのように聞こえます。{1..n}すべての順列の集合を再帰的に定義する方法、つまり の順列を の順列で表現する方法について考えてみてください{1.. n-1}。このために、n!順列があるという帰納的証明を思い出してください。誘導ステップはそこでどのように進行しますか?

于 2013-11-10T20:28:52.510 に答える