佳能2900驱动下载-acdsee序列号
![全排列算法](/uploads/image/0831.jpg)
2023年4月4日发(作者:红蓝对抗)
c语⾔字典序算法就是全排列么,全排列算法分析(原创⽅法⼀
般⽅法字典序法)...
问题重述:
全排列算法即对给定的⼀个序列,输出其所有不同的(n!种)排列,例如:
给定序列{1,2,3}有{1,2,3}、{1,3,2}、{2,1,3}、{2,3,1}、{3,1,2}、{3,2,1}这6种排列
好像很容易就能写出来,对于更长的序列也只是时间问题,最终肯定能够⽤笔⼀⼀列出来。但是要⽤程序实现的话,可能让⼈有点⽆从下⼿
(乍看好像很简单),下⾯给出三种不同的解全排列的⽅法:
⼀.原创⽅法
所谓的原创⽅法就是不考虑算法的效率及其他因素,完全为了解决问题⽽⾃⼰去构造⼀种可⾏的⽅法(不⼀定好,但能解决问题)
⾸先,让我们想想⾃⼰是如何写出上⾯的6个序列的确定第⼀位上的元素,有三种可能:1,2,3
确定第⼆位上的元素(以1为例),有两种可能:2,3
确定第三位上的元素(以2为例),只有⼀种可能:3。这时我们就得到了⼀个序列:1,2,3
接下来,让我们理⼀理思路,想想⽤程序如何实现。对于⼀个长度为n的序列来说,计算机要做的就是:1.确定第(i)位上的元素,有(n+1
–i)种可能,依次选择⼀种可能作为第i位的元素,保存当前已经确定的序列(长度为i)
2.确定第(i+1)位上的元素,有(n+1–i–i)种可能,依次选择⼀种可能作为第i+1位的元素,保存当前已经确定的序列(长度为i+1)
。。。
n.确定第(n)位上的元素,只有⼀种可能,将唯⼀的可能元素作为第n位上的元素,输出已经确定的序列
显然,这是⼀种递归的⽅法。Java代码如下:
publicclassFullPermutation{
staticintcount=0;
//递归实现全排列
//程序思路是:依次确定第⼀位到最后⼀位,与⼈的⼀般思维⽅式⼀致
publicstaticvoidmain(String[]args){
Stringstr="13234";
str=check(str);//去除重复元素
fullPermutate(0,"",str);
(count);
}
//@paramindex本次调⽤确定第index位
//@parampath已经确定顺序的串
//@paramstring待全排列的串
staticvoidfullPermutate(intindex,Stringpath,Stringstring)
{
StringrestStr=strSub(string,path);
if(index==())
{
n(path+restStr);
count++;//
return;
}
else
{
for(inti=0;i<()-index;i++)
fullPermutate(index+1,path+(i),string);
}
}
//@paramfull完整的串
//@parampart部分⼦串
//@returnrest返回full与part的差集
staticStringstrSub(Stringfull,Stringpart)
{
Stringrest="";
for(inti=0;i<();i++)
{
Stringc=(i)+"";
if(!ns(c))
rest+=c;
}
returnrest;
}
//@paramstr待检查的串
//@return返回不含重复元素的串
staticStringcheck(Stringstr)
{
for(inti=0;i<()-1;i++)
{
StringfirstPart=ing(0,i+1);
StringrestPart=ing(i+1);
str=firstPart+e((i)+"","");
}
returnstr;
}
}
P.S.⾄于上⾯的代码中为什么要去除参数中的重复元素,是为了增强程序的鲁棒性,经典的排列问题是针对不含重复元素的序列⽽⾔的,含
重复元素的序列我们将在后⾯展开讨论
⼆.⼀般算法(最常见的,也是最经典的全排列算法)
核⼼思想是交换,具体来说,对于⼀个长度为n的串,要得到其所有排列,我们可以这样做:把当前位上的元素依次与其后的所有元素进⾏
交换
对下⼀位做相同处理,直到当前位是最后⼀位为⽌,输出序列
(需要注意的⼀点:我们的思想是“交换”,也就是直接对原数据进⾏修改,那么在交换之后⼀定还要再换回来,否则我们的原数据就发⽣
变化了,肯定会出错)
#include
intn=0;
voidswap(int*a,int*b)
{
intm;
m=*a;
*a=*b;
*b=m;
}
voidperm(intlist[],intk,intm)
{
inti;
if(k>m)
{
for(i=0;i<=m;i++)
printf("%d",list[i]);
printf("n");
n++;
}
else
{
for(i=k;i<=m;i++)
{
swap(&list[k],&list[i]);
perm(list,k+1,m);
swap(&list[k],&list[i]);
}
}
}
intmain()
{
intlist[]={1,2,3,4,5};
perm(list,0,4);
printf("total:%dn",n);
return0;
}
原⽂也给出了⼀点解释,但如果还是不能理解的话,不妨输出⼀下运⾏轨迹,有助于理解,或者⽤笔画⼀画,多看⼏遍就明⽩了,直接看代
码的话确实不好理解
三.字典序法
其实在本⽂开头给出的例⼦中就⽤了字典序,⼈写全排列或者其它类似的东西的时候会不⾃觉的⽤到字典序,这样做是为了防⽌漏掉序列
既然如此,⽤字典序当然也能实现全排列,对于给定序列{3,1,2},我们理⼀理思路,想想具体步骤:对给定序列做升序排序,得到最⼩字
典序{1,2,3}
对有序序列求下⼀个字典序,得到{1,3,2}
如果当前序列没有下⼀个字典序(或者说当前序列是最⼤字典序,如{3,2,1}),则结束
显然字典序法的核⼼是:求下⼀个字典序,要充分理解这⾥的“下⼀个”,有两层意思:该序列在字典中是排在当前序列后⾯的
该序列是字典中最靠近当前序列的
字典序有严格的数学定义,按照定义就能求出⼀个序列的下⼀个字典序,具体做法不在此展开叙述(下⾯的代码中有细致的解释)。Java代码
如下:
publicclassDictionaryOrder{
//按字典序输出全排列
//按照字典序可以得到已知序列的下⼀个序列,可以⽤于不需要得到所有全排列的场合(例如数据加密)
publicstaticvoidmain(String[]args){
intarr[]=newint[]{4,3,1,2};
//booleanexist=nextPermutation(arr);
//if(exist)
//{
//for(intvalue:arr)
//(value);
//n();
//}
//else
//n("当前序列已经是最⼤字典序列");
//对给定序列排序(升序)
sort(arr);
for(intvalue:arr)
(value);
n();
//求全排列并输出
intcount=1;//第⼀个已经在上⾯输出了
while(nextPermutation(arr))
{
for(intvalue:arr)
(value);
n();
count++;
}
n("共"+count+"个");
}
//@paramarr当前序列
//@return字典序中的下⼀个序列,没找到则返回false
publicstaticbooleannextPermutation(int[]arr)
{
intpos1=0,pos2=0;
//1.从右向左找出满⾜arr[i]
//(就是找出相邻位中满⾜前者⼩于后者关系的前者的位置)
booleanfind=false;
for(inti=-2;i>=0;i--)
if(arr[i]
{
pos1=i;
find=true;
break;
}
if(!find)//若没找到,说明当前序列已经是最⼤字典序了
returnfalse;
//2.从pos1向后找出最⼩的满⾜arr[i]>=arr[pos1]的i
//(就是找出pos1后⾯不⼩于arr[pos1]的最⼩值的位置)
intmin=arr[pos1];
for(inti=pos1+1;i<;i++)
{
if(arr[i]>=arr[pos1])
{
min=arr[i];
pos2=i;
}
}
//3.交换pos1与pos2位置上的值
inttemp=arr[pos1];
arr[pos1]=arr[pos2];
arr[pos2]=temp;
//4.对pos1后⾯的所有值做逆序处理(转置)
inti=pos1+1;
intj=-1;
for(;i
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
returntrue;
}
//对给定数组做升序排序(冒泡法)
//@paramarr待排序数组
publicstaticvoidsort(int[]arr)
{
for(inti=0;i<-2;i++)
for(intj=0;j<-i-1;j++)
if(arr[j]>arr[j+1])
{
inttemp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
算法细节就到这⾥,下⾯讨论⼏个⽆关紧要问题:
1.给定序列中存在重复元素
经典的全排列问题不讨论这个问题,但实际应⽤中可能会遇到,我们有两个选择:
a.对原数据(给定序列)进⾏处理,对于重复元素只保留⼀个,或者对重复元素做替换,例如对{1,1,2,3,2},我们建⽴⼀张替换表,a=1,
b=2,原数据处理结果为{1,a,2,3,b},⾄此我们就消除了重复元素
b.对算法做修改,检测重复元素并做相应处理,需要结合具体数据特征做处理
2.算法效率问题
如果复杂问题中需要⽤到全排列,那么不得不考虑算法效率问题了,上⾯给出的算法中,前两种时间复杂度相同,都是n层递归,每层n-i+
1个循环
第三种算法的时间复杂度主要集中在了排序上,如果给定序列已经有序,那么此时第三种算法⽆疑是最佳的
更多推荐
全排列算法
发布评论