问题
假设有 {1, 2, 3, ... n} 这样一个序列, 找出这个序列的所有全排列.
求解思路
第一位有 n 种可能性, 确定了第一位后就是求解剩下 n - 1 个数据的排列问题, 这样就可以往下一直分解问题, 直到序列结尾处, 也就是终止条件.
第 1 位排列情况 (无递归)
- 2 3
- 1 3
- 2 1
暂不考虑序列元素重复问题, 测试序列 {1,2,3}
- #include <iostream>
- using namespace std;
- void Perm(int list[],int from,int n)
- {
- for (int i = from;i <n;i++)
- {
- swap(list[from], list[i]);
- // 交换一次输出一次全排列
- for (int i = 0;i < n;i++)
- cout << list[i] << " ";
- cout << endl;
- // 保证交换之前的序列还是 {1, 2, 3}
- swap(list[from], list[i]);
- }
- }
- int main()
- {
- int list[] = { 1,2,3 };
- Perm(list, 0, 3);
- return 0;
- }
所有的排列情况 (递归第 2 位, 第 3 位)
- 1 2 3
- 1 3 2
- 2 1 3
- 2 3 1
- 3 2 1
- 3 1 2
- #include <iostream>
- using namespace std;
- void Perm(int list[],int from,int n)
- {
- // 循环终止条件
- if (from == n)
- {
- // 交换一次输出一次全排列
- for (int i = 0;i < n;i++)
- cout << list[i] << " ";
- cout << endl;
- return;
- }
- for (int i = from;i < n;i++)
- {
- swap(list[from], list[i]);
- // 加入递归
- Perm(list, from + 1, n);
- // 保证交换之前的序列还是 {1, 2, 3}
- swap(list[from], list[i]);
- }
- }
- int main()
- {
- int list[] = { 1,2,3 };
- Perm(list, 0, 3);
- return 0;
- }
来源: https://www.cnblogs.com/zhongweizi/p/12465240.html