思想:
- n 个元素数组全排列 = 第 1 个前缀 + 后 n - 1 个元素全排列
- 输出第 k 个元素之后的全排列:
- 首先输出以 k 为前缀, 后 n - k 个元素的全排列
- 然后依次将第 k 个元素与其后的元素互换,再进行后 n - k 个元素的全排列
- 每一次互换 -> 排列之后,要互换恢复数组,以便于 k 与其后其他元素互换
- 用递归实现,递归到最后一个数时候输出整个数组
#include <iostream>
using namespace std;
void perm(int list[], int k, int m)
{
if (k == m) //递归到最后一个数,输出list
{
for (int i = 0; i < m; i++) {
cout<<list[i]<<" ";
}
cout<<endl;
return;
}
for (int i = k; i < m; i++) //第一次自己和自己换
{
swap(list[k], list[i]);
perm(list, k + 1, m);
swap(list[k], list[i]); //还原数组
}
}
int main()
{
int list[] = {1,2,3,4,5,6} ;
perm(list, 0, sizeof(list) / sizeof(int));
return 0;
}