Question

关于数组全排列的递归方法实现的程序思路

问题出自linux C 一站式编程网站，原题如下：
定义一个数组，编程打印它的全排列。比如定义：

#define N 3
int a[N] = { 1, 2, 3 };

则打印出
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
1 2 3
程序的主要思路是：

把第1个数换到最前面来（本来就在最前面），准备打印1xx，再对后两个数2和3做全排列。

把第2个数换到最前面来，准备打印2xx，再对后两个数1和3做全排列。

把第3个数换到最前面来，准备打印3xx，再对后两个数1和2做全排列。

可见这是一个递归的过程，把对整个序列做全排列的问题归结为对它的子序列做全排列的问题，注意我没有描述Base Case怎么处理，你需要自己想。你的程序要具有通用性，如果改变了N和数组a的定义（比如改成4个数的数组），其它代码不需要修改就可以做4个数的全排列（共24种排列）。

解题过程：

(1) 当 N = 1的时候，则直接打印数列即可。

(2) 当 N = 2的时候，设数组为 [a, b]

打印a[0], a[1] （即a，b）

交换a[0],a[1]里面的内容

打印a[0],a[1] （此时已变成了 [b, a] ）

(3) 当 N = 3的时候，数组为 [a, b, c]

把a放在 a[0] 的位置（原本也是如此，a[0] = a[0]），打印b,c的全排列（即a[1], a[2]的全排列）
a b c

a c b

把b放在a[0]的位置（这时候需要交换原数组的a[0]和a[1]），然后打印a, c的全排列
b a c

b c a

打印完后再换回原来的位置，即a还是恢复到a[0]，b还恢复到a[1]的位置

把c放在a[0]的位置（这时候需要交换的是原数组的a[0]和a[2]），然后打印a, b的全排列
c b a
c a b
打印完后再换回原来的位置，即a还是恢复到a[0]，b还恢复到a[1]的位置
至此，全排列完成
当 N = 4，5，6,……的时候，以此类推。
代码：
#include <stdio.h>
#define N 3

int a[N];

void perm(int); /*求数组的全排列 */
void print();
void move(int, int);

int main(){
int i,n;
int offset; /* 从第offset个数开始排列 */
for(i = 0; i<N; i++){
a[i] = i + 97;
}
perm(0);
}

void perm(int offset){
int i, temp;
if(offset == N-1){
print();
return;
}else{
for(i = offset;i < N; i++){
move(i, offset);
perm(offset + 1);
move(i, offset);
}
}
}

void print(){
int i;
for(i = 0; i < N; i++)
printf(" %c ",a[i]);
printf("\n");
}

void move(int i, int offset){
int temp;
temp = a[offset];
a[offset] = a[i];
a[i] = temp;
}

程序我能看懂，可让我想我死活想不出来，谁能告诉我他的程序每一变量的设定是个什么思路。

Answer 1

每次嵌套perm都会定义int i, temp;，所以这两个变量定义了很多次。每次执行到右大括号或者return的时候，本次定义的i和temp会析构。并且返回后会接着perm(offset + 1);这句执行。这时的offset跟return之前的那个offset没有关系，不要受影响，不过你很容易忘掉这时的offset是属于哪个perm的。
所以程序的思想还是最重要的，只看程序只会眼花。我总结了下，这个程序主要思想是（N=4，排列a b c d 为例）
前二个不变，先排列后面的两位，只有两种情况 c d和 d c；a不变，b和c交换位置，还是排列后两位，还是两种情况 b d和 d b；a不变，b和d交换位置,排列后两位，两种情况c b和b c；后3位的6种情况全有了。a与b交换位置，排列a c d，还是6中情况，这样下去共24种情况。核心思想是总是处理n-1次的排列，归根结底还是2个数的排列。
这属于算法的范围了，如果随便就让你想出来，那还要搞学术的干毛？学习语言嘛，淡定点，会用就行了，算法会有人搞的

Answer 2

perm(int offset)从offset位开始做全排列；
move(int i, int offset)将第i个数和第offset数对调位置。
然后递归，有什么不明白的地方？

追问

想问他的思路，变量值得设定，怎么想出这个办法的，具体点。。。

追答

你前面不是写了思路吗，不就是递归，你具体什么地方不明白？

Answer 3

你设置了阈值判断吧，可以输出多个二进制数如0001则属于1,0010=2,0100=3,1000=4，用这种方法转换