求全排列问题的算法

时间:2021-08-23 13:54:39
//全排列问题,近期面试的热门考题,收录于此
/*
设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中唯一的元素;
当r>1时,Perm(R)由(r1)Perm(r1),(r2)Perm(r2).....(rn)Perm(rn)构成.
依此递归定义,Perm(R)的递归算法如下:
*/

#include <iostream>
#include <cstdlib>

using namespace std;

void swap(int & a,int & b)
{
int temp=a;a=b;b=temp;
}

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]);
}
}

int main()
{
int list[]={1,2,3,4,5,6};
Perm(list,0,3);
system("pause");
return EXIT_SUCCESS;
}

/*
算法Perm(list,k,m)递归地产生所有前缀是list[0:k-1],且后缀是list[k:m]的全排列的所有排列
*/