欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

全排列总结

程序员文章站 2022-03-22 19:06:51
...

马上蓝桥杯省赛了… 菜鸡又是去当分母的…
把一些基础的算法都总结一下,当作复习了

首先最简单的是用stl中的next_permutation和prev_permutation了
next_permutation(start,end) 是输出下一个排列,所以用之前要对数组进行从小到大排序

void Perm(int*  a,int  n)
{
    sort(a+1,a+n+1);
    do{
        for(int i=1; i<=n; i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }while(next_permutation( a + 1, a + n + 1)); //下一个排列
}

prev_permutation需要从大到小排序,并且是逆着输出全排列

bool cmp(const int a,const int b){
return a>b;}
void Perm(int*  a,int  n)
{
    sort(a+1,a+n+1,cmp);
    do
    {
        for(int i=1; i<=n; i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }while(prev_permutation( a+1, a + n + 1)); //下一个排列

}

下面说说如何手写实现全排列

显示简单的回溯法生成,但是不是字典序,每次交换相邻的两个值就好了。

void Perm(int*  a,int cur,int  n)
{
   if(cur==n){
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
   }
   else
   for(int j=cur;j<n;j++){
        swap(a[cur],a[j]);
        Perm(a,cur+1,n);
        swap(a[cur],a[j]);
   }
}

然后是字典序的全排列

void Perm(int * a,int cur ,int n){
	if(cur==n){
		for(int i=0;i<n;i++){
			cout<<a[i]<<" "; 
		}
		cout<<endl;
	}
	else 
	for(int i=1;i<=n;i++){ //给数组填数 
		int ok=0;
		for(int j=0;j<cur;j++){
			if(a[j]==i) ok=1;
		}
		if(!ok){
			a[cur]=i;
			Perm(a,cur+1,n);
		}
	}
}

单个搜索给数组填数就好了。也比较简单。

显然,上面的算法就决定了这种方式无法输出有重复元素的全排列,因为我们选择了没有出现过元素。
我们只要改进算法,计算该元素的个数以及之前使用过的个数进行比较,如果不相等就可以使用

void Perm(int * a,int cur ,int n){
	if(cur==n){
		for(int i=0;i<n;i++){
			cout<<a[i]<<" "; 
		}
		cout<<endl;
	}
	else 
	for(int i=0;i<n;i++) if(!i||p[i]!=p[i-1]){ //给数组填数 
		int c1=0,c2=0;
		for(int j=0;j<cur;j++) if(a[j]==p[i]) c1++;
		for(int j=0;j<n;j++) if(p[i]==p[j]) c2++;
		if(c1<c2){
			a[cur]=p[i];
			Perm(a,cur+1,n);
		}
	}
}
相关标签: 全排列