©2020-2024 ioDraw All rights reserved,
Privacy Policy
参照计算机算法设计与分析（第5版）
这个代码跑在vs2017上的，如果其他ide我不保证一定一样，本文的初衷在于帮助数学不好的递归初学者（和用不来断点的老哥：事实上断点也不好整，容易看到心态爆炸）用顺序阅读的形式来简单理解递归
当然：
说白了递归就是栈，本文面向对象是栈都没学的新人那种
<>我的递归代码（无重复元素可用）
#include<iostream> using namespace std; int res = 0;//数数用 void Swap(char &a,
char&b) { if (a == b) ; else { char temp = a; a = b; b = temp; } } void Perm(
char brr[], int k , int m) // k：变量，表示运行到第几个数了 m: 常量，需要排列的数组 { if (k == m) { for
(int i = 0; i <= m; i++) { cout << brr[i]; } cout << endl; res += 1; } else {
for (int i = k; i <= m; i++) { Swap(brr[k], brr[i]); Perm(brr, k + 1, m); Swap(
brr[k], brr[i]); } } } int main() { char arr[] = "abc"; Perm(arr, 0, 2); cout <<
res<< endl; system("pause"); return 0; }
<>然后是按步来推导递归的伪代码
首先：每一个Perm()的构成为： 输出：Perm() if 过程：Perm() else for swap 下一级Perm swap for（如果有）
swap 下一级Perm swapPerm(arr,k,m)：这个代表进入了下一层函数 Arr:数组 K:当前的位置 M:需要排列的总长度（从0开始算）
主函数部分： Char arr[] = ‘abc’ Perm(arr,0,2) 进入Perm_1(arr = ‘abc’,k = 0,m = 2) Else
For i:0 k:0 无效Swap Perm_2_1(arr = ‘abc’,k = 1,m = 2): Else For i: 1 k:1 无效swap
Perm_3_1(arr = ‘abc’,k = 2,m = 2) If:cout<<”abc” 无效swap For i:2 k:1 Swap(2,1)->
arr:”acb” Pern_3_2(arr = ‘acb’,k=2,m=2) If:cout<<”acb” Swap(2,1)->arr:’abc’
无效swap For i:1 k :0 Swap(1,0)->”bac” Perm_2_2(arr = ‘bac’, k = 1,m = 2) Else
For i:1 k:1 无效swap Perm_3_3(arr = ‘bac’,k = 2,m = 2) If:cout<<”bac” 无效swap For i
:2 k:1 Swap(2,1)->’bca’ Perm_3_4(arr = ‘bca’ , k = 2 , m = 2) If:cout<<”bca”
Swap(2,1)->‘bac’ Swap(1,0)->”abc” For i:2 k:0 Swap(2,0)->”cba” Perm_2_3(arr =
‘cba’, k = 1,m = 2) Else For i:1 k:1 无效swap Perm_3_5(arr = ‘cba’ k = 2, m =2) If
:cout<<”cba” 无效swap For i:2 k:1 Swap(2,1)->”cab” Perm_3_6(arr = ‘cab’ k = 2,m =
2) If:cout<<”cab” Swap(2,1) ->”cba” Swap(2,0)->"abc" Perm_1 结束 主函数 return0 over
补充下介绍，这玩意是个伪代码，我按缩进形式表现出来的，可以看出来
1：第一个swap的作用：真就是交换，这个应该没啥问题
2：第二个swap的作用：递归完了把整个恢复原样：’abc‘
(不是必要的，但是这是个好习惯，这个全排列不加是可以得到同样个数但是不同顺序的答案，但是dfs这些你咋办。。)
补充个全排列的个数计算：
(m+1-k):for循环的个数
当k==m的时候是最后一层（也就是1），这时候就到了perm的if条件，直接输出
那么第4层就是第一层的(m+1-k)*第二层的(m+1-k)*第三层的(m+1-k)*第四层的(m+1-k) = 4X3X2X1 = 24
说白了就是n！
感觉像是废话。。因为我是在拿结果推过程hhh
希望能帮到大家，一同学习，有错误欢迎指正