全排列算法

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个循环

第三种算法的时间复杂度主要集中在了排序上，如果给定序列已经有序，那么此时第三种算法⽆疑是最佳的