全排列生成算法- 维基百科，自由的百科全书

全排列的生成算法方法是将给定的序列中所有可能的全排列无重复无遗漏地枚举出来。

此处全排列的定义是：从n个元素中取出m个元素进行排列，当n=m时这个排列被称为全排列 ... 全排列生成算法 维基百科，自由的百科全书 跳到导航 跳到搜索 此條目包含指南或教學內容。

(2017年6月20日)請藉由移除或重寫指南段落來改善條目，或在討論頁提出討論。

全排列的生成算法[1]方法是将给定的序列中所有可能的全排列无重复无遗漏地枚举出来。

此处全排列的定义是：从n个元素中取出m个元素进行排列，当n=m时这个排列被称为全排列。

字典序、邻位对换法、循环左移法、循环右移法、递增进位制法、递减进位制法都是常见的全排列生成算法。

目录 1字典序法 1.1算法步骤 1.2算法正确性证明 1.3例子 2插入法 3邻位对换法 3.1算法步骤 3.2算法正确性证明 4递增进位制法 4.1算法步骤 4.2算法正确性证明 5递减进位制法 5.1算法步骤 5.2算法正确性证明 6实例：给定一个排列求后面或者前面的某个排列 7参考资料 字典序法[编辑] 字典序，就是将元素按照字典的顺序（a-z,1-9）进行排列。

以字典的顺序作为比较的依据，可以比较出两个串的大小。

比如"1"“123456798”->......->"987654312"->"987654321"这样的串。

字典序法要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

[2] 算法步骤[编辑] 设P是集合{1，2，……n-1，n}的一个全排列：P=P1P2……Pj-1PjPj+1……Pn（1≤P1，P2，……，Pn≤n-1） 从排列的右端开始，找出第一个比右边数字小的数字的序号j，即j=max{i|Pij} 在Pj的右边的数字中，找出所有比Pj大的数字中最小的数字Pk，即k=min{i|Pi>Pj，i>j} 交换Pj，Pk 再将排列右端的递减部分Pj+1Pj+2……Pn倒转，因为j右端的数字是降序，所以只需要其左边和右边的交换，直到中间，因此可以得到一个新的排列P'=P1P2……Pj-1PkPn……Pj+2Pj+1。

算法正确性证明[编辑] 证明它可以生成所有的排列只需要证明生成的下一个排序恰好比当前排列大的一个序列即可。

对于任意j，作为从右端开始第一个小于右边数字的数，可以得到序列Pj+1，...Pn是降序排列，选择其中大于Pj的最小的数字Pk，与其交换，然后再对后面排序得到序列P1，...Pj-1Pk...Pn，恰好比P1...Pj-1Pj...Pn大一点的下一个排列，因此算法可以生成全排列。

例子[编辑] 对于元素集合{1，2，3}按字典序生成的全排列是:123,132,213,231,312,321。

//array必须是从小到大排好序的 booleandictSeq(int[]array){ //从最右端开始第一个比右边小的位置 intj=-1; for(inti=array.length-2;i>=0;i--){ if(array[i]array[j]&&array[i]<=min){//这里要找到最后一个，否则对于存在相同元素的集合会出现错误。

如：0122 min=array[i]; k=i; } } //交换j和k的值 inttmp=array[j]; array[j]=array[k]; array[k]=tmp; //对j后边的序列进行反转 intleft=j+1; intright=array.length-1; while(left