全排列

生成全排列的三种方法

该函数生成全排列时需要注意原数组本身需要排好序，并且没有重复元素，否则生成的结果会有重复。

void Permutation(int k,int a[],int len){
	if(k==len){
		for(int i=0;i<len;i++){
			cout<<a[i]<<' ';
		}
		cout<<endl;
		return;
	}
	for(int i=k;i<len;i++){
		swap(a[i],a[k]);
		Permutation(k+1,a,len);
		swap(a[i],a[k]);
	}
}

该法可以生成即使数组中有重复元素也仍然可以让结果不重复的全排列

void _Permutation(int k,int a[],int len,bool vis[],int path[])
{
	if(k==len)
	{
		for(int i=0; i<len; i++)
		{
			cout<<path[i]<<' ';
		}
		cout<<endl;
		return;
	}
	for(int i=0; i<len; i++)
	{
		if(i>0&&a[i-1]==a[i]&&!vis[i-1])continue;
		if(!vis[i])
		{
			vis[i]=true;
			path[k]=a[i];
			_Permutation(k+1,a,len,vis,path);
			vis[i]=false;
		}
	}
}

在c++中，在头文件下有全排列函数next_perputation()所以可以直接通过该函数生成去除重复元素的全排列。

void Permutation_2(int a[],int len)
{
	do
	{
		for(int i=0; i<len; i++)
		{
			cout<<a[i]<<' ';
		}
		cout<<endl;
	}while(next_permutation(a,a+len)); 
}