递归算法之全排列问题

问题描述

设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列（n!种）。
设R={r1,r2,…,rn}是要进行排列的n个元素，
Ri=R-{ri}。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。

分析

当n=1时，
perm®=®，其中r是集合R中唯一的元素；
当n>1时，perm®由
(r1) perm(R1)
(r2) perm(R2)
…
(rn) perm(Rn)构成。、

代码

//产生从元素k～m的全排列，作为前k-1个元素的后缀
void Perm(int list[], int k, int m){	//构成了一次全排列，输出结果
	if(k==m){
		for(int i=0;i<=m;i++)
			cout<<list[i]<<" ";
		cout<<endl;
	}
	else	//在数组list中，产生从元素k～m的全排列
		for(int j=k;j<=m;j++){
			swap(list[k],list[j]);
			Perm(list,k+1,m);
			swap(list[k],list[j]);
		}
}

数组list[]＝{1, 2, 3, 4, 5, 6,7}，则调用Perm(list,0,3) 就是产生元素1～4的全排列。

void Perm(int list[], int k, int m){
   if(k==m){
      for(int i=0;i<=m;i++)
         cout<<list[i]<<" ";
      cout<<endl;
   }
  else	
    for(int j=k;j<=m;j++)  {
       swap(list[k],list[j]);
     Perm(list,k+1,m);
       swap(list[k],list[j]);
   }
}

数组list[3]＝{1, 2, 3}

排列结果如下：