分治算法——排列问题
2011-08-05 15:10:52| 分类：分治算法|字jm号大中小订阅
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。

分析：设R={r 1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。

,集合X中元素的全排列记为perm(X)。

其中(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。

R的全排列可归纳定义如下：
当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；
当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn )perm(Rn)构成。

思路是递归产生前缀是list[0:k-1]，且后缀是list[k:m]的全排列的所有排列。

……算法将list[k:m]中每一个元素分别与list[k]中元素交换。

然后递归地计算list[k+1:m]的全排列，并将计算结果作为list[0:k]的后缀。

1）切记Perm(list,k,m)是产生从k开始到m结束的所有全排列，这个很重要。

要产生所有全排列，只要调用这个函数就行了，至于这个函数怎么实现，先不要去管。

（一开始理解递归函数的时候，由于过多的在意函数的流程，而忘了函数本身的功能。

）
2）将有限个元素的全排列分成前缀和后缀两部分。

用一个元素作前缀，剩下元素作后缀。

显然作前缀的一个元素可以是所有元素的任意一个，对前缀位置的元素作一轮交换即可。

先确定了一个前缀，然后对后缀元素们求全排列（不要关心怎么求全排列。

对后缀元素求全排列，就是原问题的一个子问题，分治法的一个特征。

）这样就得到了一个确定前缀的所有全排列。

贴上自己写的代码：
#include <stdio.h>
#include <string.h>
//包含的头文件
void swap(char &a,char &b)//实现元素的互换
{
char temp;
temp=a;
a=b;
b=temp;
}
void Perm(char str[],int k,int m) //核心代码
{
int i;
if(k==m) //产生str[k:m]的排列
{//当k==m的时候会产生一个排列，输出此排列即可
for(i=0;i<=m;i++)
printf("%c",str[i]);
printf("\n");
}
else
{
for(i=k;i<=m;i++)
{
swap(str[i],str[k]);//交换元素
Perm(str,k+1,m);//求子问题，后缀元素的全排列
swap(str[i],str[k]);//求完了子问题，将前面交换了的元素换回来，以进行下一个交换
}
}
}
int main()
{
int n,i;
char a[100]={'a','b','c'};
while(scanf("%d",&n)!=EOF)
{
getchar();
for(i=0;i<n;i++)
a[i]=getchar();
Perm(a,0,n-1);
}
return 0;
}
别人的总结，写的很好：
1）判断一个问题是否可以用递归求解。

2）建立递归定义。

数学模型的建立应该是最大的难点，如同动态规划方程的建立。

在这个阶段不要过多的考虑实现问题。

3）递归函数的定义与实现。

实现的时候有一个至关重要的地方是确定递归终止条件。

4）对递归程序的理解是，不过早的纠结在递归内部，一来是比较抽象，二来不利于理解整体思路。

而应该先理清程序的整体思路，然后才是深入追踪递归。