递归方法的副码打印$ N $给定整数的所有排列
-
28-09-2020 - |
题
我真的不明白这个伪代码。该函数打印 $ 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])
. 解决方案
您的过程会产生输入的所有排列,最后将其返回到其原始状态。
当输入有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 $ 返回。
不隶属于 cs.stackexchange