早上还在床上的时候，用手机看到了博客园上一个全排列算法。刚才，出去晒了一下太阳，突然想起那个全排列算法，
感觉还是比较的繁琐。回来后，我仔细分析了一个这个问题，觉得，实际上，3行代码就可以解决这个问题了。
顺便，也说说，递归问题的一般解决思路吧。
这个问题，非常明显，是一个 n! 复杂度的程序，如果是这样，基本上的递归结构是这样的。
f(n) = n * f(n-1)
看到这样的问题，典型的结构 应该就是 这样的结构：
f(n)
{
for (i = 0; i < n; i++)
{
f(n-1)
}
}
退出条件就是 n = 0;
当然，递归问题，必须有：
1. 结束条件
2. 递推公式
这样，首先看递推公式。
首先对位置进行编号：(因为数组下标从 0开始，那就从0 开始吧)
0, 1, 2, 3, 4, 5
里面填一些数，显然，填什么不重要，假设
a, b , c, d, e, f
好了
如果让问题规模小1 呢？
很多递归问题，其实都是可以这样分析的，假设 n - 1 的都已经算好了，
如果你没有思路，我刚开始也没有，其实，你只要在纸上画出 f(n-1) 的所有可能性（要按照一定的思路列出）。
不要怕烦，写代码的思路就是这样出来的（当然，天才或许有灵感）
a 没有：b , c, d, e, f
b 没有：a, c, d, e, f
c 没有：a, b, d, e, f
d 没有: a, b, c, e, f
e 没有：a, b, c, d, f
f 没有: a, b, c, d, e
我写完之后，感觉就是把这f(n-1)的可能性加起来，就是所有的可能性。
就想起数学里面计算排列数的方法：
叫做乘法原理，如果一件事情，可以通过n 步完成：
第一步：
第一个位置有n 种可能，大家都可以放。
第二步：
第二个位置有n-1 种可能，因为，第一个位置定下来了。
...
最后，一步，大家都定下来了，那么最后一个位置就只能放剩下来的那个了。
虽然，这个计算过程是一步，一步的，像是一种顺序结构。但是，也可以认为是一种递归结构。
用程序模拟就是：
第一个位置 如果是a ，下面就是 f(n-1) 的问题了。
第一个位置 如果是b, 下面也是f(n -1) 的问题了
...
接下来，你就是绞尽脑子，怎么模拟这个过程了。
最后想到了交换比较的好。
就是按照顺序把元素交换到pos 位置，
交换后，对f(n-1) 进行处理
然后再交换回来，对下一个元素进行交换。
直接给出代码：
#define swap(arr, i , j)\
{\
if ((i) != (j)) {\
int temp;\
temp = arr[i]; \
arr[i] = arr[j]; \
arr[j] = temp;\
}\
}
void print_array(int *arr, int len)
{
int i;
printf("\n");
for(i =0; i < len; i++) {
printf("%d ", arr[i]);
}
}
int permutation(int *arr, int pos, int n)
{
int i;
if (pos == n) { //递归结束条件
print_array(arr, n);
return;
}
for(i = pos; i < n; i++)
{
swap(arr, i, pos);//某个数字交换到 pos 位置
permutation(arr, pos + 1, n); //对出pos 位置后面的数，进行一次全排列
swap(arr, i, pos);//复原原来的排列，准备交换下一个数到pos 位置。
}
return 0;
}
int main(int argc, char *argv[])
{
int n = 0;
int i;
int number[20]; //已经有2432902008176640000 种排列方法了，输出来也很难保存这样多的数据了，所以程序不能大于这个数字。
printf("input n: ");
while (scanf("%d", &n)) {
if (n < 1) {
printf("n must big than zero. \n");
continue;
}
if (n > 20) {
printf("n too big. \n");
continue;
}
for (i = 0; i < n; i++) {
number[i] = i + 1;
}
permutation(number, 0, n);
printf("\n\ninput n: ");
}
return 0;
}
一般的，我给大家介绍一些递归编程中，比较常用的技巧：
1. 一般，如果，不能退到 n - 1，必须退到 n - 2 和 n -1 组合才行的，一般不要用递归。否则，计算复杂性一般都很高。
2. 如果，你觉得一个问题可以 用nlogn 的复杂性来解决，一般验证一下：把问题对半，然后，看看，两个只问题能合并成
这个问题的解需要多少的计算量。如果是2f(n/2) + n 那么，问题就是nlogn 的复杂度，如果，n是线性的，或者是常数，
可以考虑递归，否则，就不要考虑了，复杂度一般会很高。
3. 如果一个问题，可以在n的复杂度内解决，一般来说，递归的时候，是常数级别的运算。这样的问题很多，常见的算法
是动态规划的算法。
很多时候，用你对一个问题复杂度的直觉，倒推出算法，是一种很有意思的方法。特别是应付考试，那是相当的有效。
（很多考试题，会要求 复杂度 是多少以内）