递归方法的副码打印$ 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] $ < / span>。

以下是程序所做的：

• 输出 $ 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] $ 。

在第一步中，该过程仅介绍了列表尾部的所有排列，包括除了第一个元素之外的所有。

在第二步中，它切换 $ a_1 $ 和 $ a_2 $ ，遍历所有排列尾部，然后切换 $ a_1 $ 和 $ a_2 $ 返回。

在第三步中，它切换 $ a_1 $ 和 $ a_3 $ ，遍历所有排列尾部，然后切换 $ a_1 $ 和 $ a_3 $ 返回。

等，直到 $ n $ th步骤，它切换 $ a_1 $ 和 $ a_n $ ，遍历尾部的所有排列，然后切换 $ a_1 $ 和 $ a_n $ 返回。