全排列解析
10 26, 2008 Linux
今天没什么事，以前在学校一直没弄清楚全排列的实现。花了点时间研究，总算搞清楚了整个过程。基本思路：设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}.集X中元素的全排列记为Perm(X),(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳定义如下:
当n=1时,Perm(R)={r},r是集合R中唯一的元素.
当n>1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),….(rn)Perm(Rn)构成
代码如下(采用的测试数据为{1, 2, 3, 4})：
#include <stdio.h>
#include <stdlib.h>
void perm(int a[], int start_pos, int end_pos);
void swap(int *start, int *internal);
int main(void)
{
int a[4] = {1, 2, 3, 4};
int start=0, end=0;
perm(a, 0, 3);
return 0;
}
void perm(int a[], int start_pos, int end_pos)
{
int i, j;
if (start_pos == end_pos) /* recursive end */
{
for (j=0; j<=end_pos; ++j) /* print the array… */
{
printf(”%5d”, a[j]);
}
printf(”\n”);
}
for (i=start_pos; i<=end_pos; ++i)
{
swap(a+start_pos, a+i);
perm(a, start_pos+1, end_pos);
swap(a+start_pos, a+i); /* swap back… */
}
return ;
}
void swap(int *start, int *internal)
{
int temp;
temp = *start;
*start = *internal;
*internal = temp;
return ;
}
递归其实就是数学归纳法的逆过程，数学归纳法是递推，递归则相反（这点我自己领悟到的，^_^）。证明当n=k-1时命题成立相当于递归过程的一个调用，递归终点也就相当于归纳法中的当n=1时命题成立。好了，现在把问题放在全排列上，其实大概的过程我们都可以自己拿支笔演算出来，我们把问题放在程序的核心部分： for (i=start_pos; i<=end_pos; ++i)
{
swap(a+start_pos, a+i); /* 交换1 */
perm(a, start_pos+1, end_pos);
swap(a+start_pos, a+i); /* swap back… */ /* 交换2 */
}为什么要交换回去，交换一次不就可以了？我把交换2注释掉把程序跑了一遍，出现重复现象，以下是测试结果：
1 2 3 4
1 2 4 3
1 4 2 3
1 4 3 2
1 2 3 4
1 2 4 3
2 1 4 3
2 1 3 4
2 3 1 4
2 3 4 1
2 1 4 3
2 1 3 4
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
3 1 2 4
3 1 4 2
2 1 4 3
2 1 3 4
2 3 1 4
2 3 4 1
2 1 4 3
2 1 3 4
出现了重复现象，追其原因，递归到终点打印出了排列序列以后，返回到上一级调用。当r1=1,R1={2, 3, 4}时，函数调用本身perm(R1)，直接写出排序吧，2, {3, 4}…2, {4, 3}，打印出这两个排列（{1, 2, 3, 4}跟{1, 2, 4, 3}）后，返回到上一级调用，由于我们把交换2去掉了，所以这时内存中该数组的排列是{1, 2, 4, 3}，这个不会随着函数返回而改变，下一个循环，这时该交换2跟4了，刚刚交换的是2跟自己本身，接下来看排列，4, {2, 3}…4, {3, 2}，打印出这两个排序（{1, 4, 2, 3}跟{1, 4, 3, 2}）后，返回到上一级调用，这时内存中该数据的排列是{1,4,3,2}，这时接着一下个循环，末尾2跟4交换，变成2, {3, 4}跟2, {4, 3}，打印出排列，分别是{1, 2, 3, 4}跟{1, 2, 4, 3}，跟前面重复了，而避免出现这种情况的方法就是交换2需要加到程序里面，把当时交换的数据重新交换回去，这样后面的排列可以保证不出现重复现象，这里就不把运行过程重复了，就按照前面的方法分析就可以。所以很多时候，我们多点耐心，仔细地分析程序，收获会很大。
来说两句吧