$ n $が与えられた整数のすべての順列を印刷する再帰的方法の疑似コード

Question

私は本当にこの疑似コードを理解していません。この関数は、すべての数字が異なると仮定して、 $ n $ のすべての順列を印刷します。

このコードを簡単に説明する方法は、スワッピングの目的をしないように簡単に説明します。

PERMUTATE(A, start, end)
   if start == end return A
   else
      PERMUTATE(A,start+1,end)
      for i = start+1 to end
         SWAP(A[i],A[start])
         PERMUTATE(A,start+1,end)
         SWAP(A[start],A[i])

.

Answer 1

あなたの手順は入力のすべての置換を生み出し、それを最後に元の状態に戻します。

入力が長さ1のときには何もしない。

それ以外の場合は、入力が $ a_1、\ ldots、a_n $ であるとします。 $ a_1、\ ldots、a_n $ のすべての順列を表す $ [a_1、\ ldots、a_n] $ <$ <$ < /スパン>

これは手順が何であるかです。

• 出力 $ a_1、[a_2、a_3、\ ldots、a_ {n-1}、a_n] $ 。
• 出力 $ a_2、[a_1、a_3、\ ldots、a_ {n-1}、a_n] $ 。
• 出力 $ a_3、[a_2、a_1、\ ldots、a_ {n-1}、a_n] $ 。
• ...
• 出力 $ a_n、[a_2、a_3、\ ldots、a_ {n-1}、a_1] $ 。

最初のステップでは、この手順は単にリストの末尾のすべての順列を超えて、最初の要素全てからなる。

2番目のステップでは、 $ a_1 $ と $ a_2 $ を切り替えます。テールのうち、 $ a_1 $ と $ a_2 $

3番目のステップでは、 $ a_1 $ と $ a_3 $ を切り替えます。テールのスイッチを切り替えて、 $ a_1 $ と $ a_3 $

$ n $ の場合、 $ a_1 $ を切り替えるまで $ a_n $ は、末尾のすべての置換を覆い、次に $ a_1 $ と $ A_n $ 背面