求全排列最简单的就是递归了
123 的全排列共有 6 个， 123 的全排列等于以 1 开头 23 的全排列， 加上以 2 开头 13 的全排列，加上以 3 开头 21 的全排列。
一个数列的全排列就是每一个数分别与第一个数交换（每一个数字都做一回头）后所得数列全排列的和。去掉第一个数字，后面数列的全排列怎么求？？？显然一样的求法，递归就行。
什么时候结束递归呢？？？显然当只剩下一个数字的时候就求得了一个全排列。
permutation.jpg
#include <cstdio>
void swap(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void permutation(int a[], int begin, int end) {
if (begin == end - 1) {
for(int i=0; i<end; i++) {
printf("%d",a[i]);
}
printf("\n");
return;
}
// 后面的数依次与第一个数交换
for(int i=begin; i<=end-1; i++) {
swap(a, begin, i); // 包括自己和自己交换
permutation(a, begin+1, end); // 递归处理第一个数后面数列的排列
swap(a, begin, i); // 得到一个排列后再把原来交换的数换回来，开始下一个排列的计算
}
}
int main() {
int a[3] = {1,2,3};
permutation(a,0,3);
return 0;
}
关于去重，例如 122，上面的算法仍然会输出 6 个数列，怎么去除重复的排列呢？？？ 网上说的是假如要交换的两个数字下标是 i, j (i 是头) 只有当 [i,j) 之间没有和 a[j] 相同的数字才交换。我也不大理解，水平太菜, 这个递归排列我都理解了好长时间？？？？
bool canSwap(int a[], int i,int j) {
// 只有当 [i,j) 之间没有和 a[j] 相同的数字才交换
for(int x=i; x<j; x++) {
if(a[x]==a[j]) {
return false;
}
}
return true;
}
// 后面的数依次与第一个数交换
for(int i=begin; i<=end-1; i++) {
if(canSwap(a,begin,i)) {
swap(a, begin, i); // 包括自己和自己交换
permutation(a, begin+1, end); // 递归处理第一个数后面数列的排列
swap(a, begin, i); // 得到一个排列后再把原来交换的数换回来，开始下一个排列的计算
}
}
