指尖世界

分享的乐趣

特殊排列的算法

类别: 动态 更新时间: 2016-02-02

[摘要:齐摆列是调集中全体元素的摆列,而且每个摆列中的元素皆没有会反复。现实运用中,借会碰到种种非凡的摆列,比方调集中一局部元素的摆列,同意元素反复的摆列等。 目前去看一看产]

全排列是集合中全部元素的排列,并且每一个排列中的元素都不会重复。实际应用中,还会遇到各种特殊的排列,例如集合中一部分元素的排列,允许元素重复的排列等。

现在来看一看产生各种特殊排列的算法。

 

递归形式的回溯算法如下:

//全排列(递归)

//输入:排列元素个数n

//输出:n个元素的全体排列

#include<iostream>

#include <iomanip>

using namespace std;

 

void perm(int *,int);

void output(int *,int);

int total;

 

int main(void)

{

freopen("in.dat","r",stdin);

int n,*p;

while(cin>>n)

{

p=new int[n];

total=0;

backdate(p,n);

}

return 0;

}

 

void backdate(int *p,int n,int k)      //递归生成排列

{

if(k==n)                     //如果排列的n个元素的值都已选定

output(p,n);             //输出排列

else                       //否则   

for(int i=1;i<=n;i++)       //1n中为p[k]选取一个值i

{

for(int j=0;j<k;j++)    //所选的i是否与已选元素的值重复

if(p[j]==i)

break;

if(j==k)             //不重复

{

p[k]=i;         //选定 

backdate(p,n,k+1); //继续为下一个元素p[k+1]选取值

}

}

}

 

void output(int *p,int n)

{

cout<<setw(5)<<++total<<": ";

for(int i=0;i<n;i++)

cout<<setw(3)<<p[i];

cout<<endl;

}

 

生成n个元素的全排列过程中,有两个必要的条件:第一,n个排列元素的之都要选定,第二,n个排列元素要互不相同。既然如此,只要有其中一个条件发生变化,或两个条件都改变,所生成的排列就不再是全排列了。因此,可以从特殊排列的要求出发,改变排列元素的检验条件,就可以生成所需要的排列。

一.从n个不同元素中区mmn)个的排列

n个不同元素中,任选m个元素的排列可称为部分排列或选排列。显然,mn。如果m=n,那么就是全排列,所以,如果不做特别说明,可以认为m<n

n个元素的全排列中,每次所选取的元素个数必须要达到元素总数n,才输出一个排列。那么,现在只要须选定m个元素,就输出一个排列,所得的排列就是一个n个元素中选取m个元素的排列了。

以回溯法的递归程序为例,只要将代码按照代码中的黑体部分改变即可。

//n个元素取m个的排列(递归)

//输入:元素总数n,排列元素个数m

//输出:n个元素取m个的全体排列

#include<iostream>

#include <iomanip>

using namespace std;

 

void perm(int *,int);

void output(int *,int);

int total;

 

int main(void)

{

freopen("in.dat","r",stdin);

int n,m,*p;

while(cin>>n>>m)

{

p=new int[n];

total=0;

backdate(p,n,m,0);

}

return 0;

}

 

void backdate(int *p,int n,int m,int k)  //递归生成排列

{

if(k==m)                      //如果排列中有m个元素的值被选定

output(p,m);              //输出排列

else                         //否则   

for(int i=1;i<=n;i++)         //n中为元素p[k]选取一个值

{

for(int j=0;j<k;j++)      //所选的值i是否与已选元素的值重复

if(p[j]==i)

break;

if(j==k)              //不重复

{

             p[k]=i;          //p[k]取值

backdate(p,n,m,k+1); //继续为下一个元素选取值

}

}

}

 

void output(int *p,int n)

{

cout<<setw(5)<<++total<<": ";

for(int i=0;i<n;i++)

cout<<setw(3)<<p[i];

cout<<endl;

}

 

二.允许元素重复的全排列

一般情形,全排列中所有的元素都不相同。如果允许排列的元素重复,那就是允许可重复的排列。对于允许重复的全排列,只需要将生成全排列的算法中,将检验排列元素重复的代码去掉即可。

//元素可重复全排列(递归)

//输入:排列元素个数n

//输出:n个元素可重复的全体排列

#include<iostream>

#include <iomanip>

using namespace std;

 

void perm(int *,int);

void output(int *,int);

int total;

 

int main(void)

{

freopen("in.dat","r",stdin);

int n,*p;

while(cin>>n>>m)

{

p=new int[n];

total=0;

backdate(p,n,0);

}

return 0;

}

 

void backdate(int *p,int n,int k)      //递归生成排列

{

if(k==n)                     //如果排列的n个元素的值都已选定

output(p,n);             //输出排列

else                        //否则   

for(int i=1;i<=n;i++)       //n中为元素p[k]选取一个值

{

// for(int j=0;j<k;j++)    //所选的值i是否与已选元素的值重复

// if(p[j]==i)

// break;

// if(j==k)             //不重复

{

p[k]=i;         //p[k]取值i  

backdate(p,n,k+1); //继续为下一个元素选取值

}

}

}

 

void output(int *p,int n)

{

cout<<setw(5)<<++total<<": ";

for(int i=0;i<n;i++)

cout<<setw(3)<<p[i];

cout<<endl;

}

 

三.指定元素可重复的全排列

如果在n个元素的全排列中,有一个元素可重复,而其余的元素不重复,生成这样的全排列。

在生成全排列的过程中,对每一个排列的元素,都要检验他是否与前面选出的元素重复,以此来保证每一个元素不会重复出现。既然如此,在要求某一个元素可以重复的情形,可以不对该元素进行重复出现的检验,它就会重复出现在排列中了。

//指定元素可重复的全排列

//输入:元素个数n,指定可重复元素x

//输出:要求的排列

#include <iostream>

#include <iomanip>

using namespace std;

 

void perm(int*,int,int,int);

void output(int*,int);

int total;

 

int main(void)

{

int n=5,x=3,*p;             //x是指定可重复的元素

p=new int[n];

fill_n(p,n,0);

total=0;

perm(p,n,x,0);

return 0;

}

 

 

void output(int *p,int n)

{

cout<<setw(5)<<++total<<":  ";

for(int i=0;i<n;i++)

cout<<setw(2)<<p[i];

cout<<endl;

}

 

void perm(int *p,int n,int x,int k)

if(k==n)                       //n个排列元素都已选定

output(p,n);              //输出

else 

for(int i=1;i<=n;i++)     

{                   

for(int j=0;j<k;j++) 

if(p[j]!=x && p[j]==i) //检查除了x以外的元素是否重复

break;        //退出循环

if(j==k)               //除了x其余元素不重复

{

p[k]=i;            //p[k]取值i     

perm(p,n,x,k+1);    //继续选取下一个元素

}

}

}

 

如果可还指定了可重复的元素的个数,则要在输出排列之前,检查该元素重复的次数,符合要求的排列就输出。

#include <iostream>

#include <iomanip>

using namespace std;

 

void perm(int*,int,int,int);

void output(int*,int);

int total;

 

int main(void)

{

int n=5,x=3,s,*p;             //x是指定可重复的元素,s是重复次数

p=new int[n];

fill_n(p,n,0);

total=0;

perm(p,n,x,s,0);

return 0;

}

 

 

void output(int *p,int n)

{

cout<<setw(5)<<++total<<":  ";

for(int i=0;i<n;i++)

cout<<setw(2)<<p[i];

cout<<endl;

}

 

void perm(int *p,int n,int x,int k)

if(k==n)                       //n个排列元素都已选定

    {

for(int i=0,t=0;i<n;i++)       //计算指定元素的重复次数 

if(p[i]==x)

t++;

if(t==s)                  //如果符合要求

output(p,n);         //输出

 

}                

else

       for(int i=1;i<=n;i++)     

{                   

for(int j=0;j<k;j++) 

if(p[j]!=x && p[j]==i) //检查除了x外的元素是否发生重复

break;        

if(j==k)               //除了x外的元素不重复

{

p[k]=i;            //p[k]取值i     

perm(p,n,x,k+1);    //继续选取下一个元素

}

}

}

注意,对重复元素重复次数的检查是在不同位置进行的,原因是重复元素的重复次数只有在排列的元素全部选定,才能正确计算。

按照类似的方法,可以实现更复杂的排列。

 

 



感谢关注 V8指尖世界精品文库频道,v8en.com是专门为互联网人打造的学习交流平台,全面满足互联网人工作与学习需求,更多互联网资讯尽在 V8指尖世界!