全排列的生成算法方法是将给定的序列中所有可能的全排列无重复无遗漏地枚举出来。此处全排列的定义是：从n个元素中取出m个元素进行排列，当n=m时这个排列被称为全排列。
字典序、邻位对换法、循环左移法、循环右移法、递增进位制法、递减进位制法都是常见的全排列生成算法。
字典序法
字典序，就是将元素按照字典的顺序（a-z, 1-9）进行排列。以字典的顺序作为比较的依据，可以比较出两个串的大小。比如 "1" “123456798”->......->"987654312"->"987654321"这样的串。字典序法要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
算法步骤
设P是集合{1，2，……n-1，n}的一个全排列：P=P1 P2……Pj-1 Pj Pj+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+1 Pj+2……Pn倒转，因为j右端的数字是降序，所以只需要其左边和右边的交换，直到中间，因此可以得到一个新的排列 P'=P1 P2……Pj-1 Pk Pn……Pj+2 Pj+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必须是从小到大排好序的
boolean dictSeq(int[] array) {
// 从最右端开始第一个比右边小的位置
int j = -1;
for (int i=array.length-2; i>=0; i--) {
if (array[i] array[j] && array[i] 。递增进位制数是指数字的进制随着位数的递增而递增。一般情况下，数字最右边的进制是2，次右边的进制是3，以此类推。n位递增进位制数一共包含n!个数字，所以它可以与全排列生成算法结合在一起。
算法步骤
由于在字典序法中由中介数求排列比较繁琐，可以通过另外定义递增进位制数加以改进。定义: i的右边比i小的数字的个数, 则()↑为递增进位制法中定义的中介数，这里的中介数是递增进位制数字。例如，839647521对应的中介数为(67342221) ↑。由中介数求排列时，从大到小根据求出n,n-1,…,2,1的位置——从右向左将第+1个空填上i，剩下的最后一个空位填上1。因此根据“原排列”→“原中介数”→“新中介数”→”新排列“，在这样的定义下，可以求出下一个排列。所以根据递增进位制法生成全排列步骤如下：
#初始化中介数（每一位都为0）
#根据中介数求出对应的排列，输出排列
#如果没有输出所有的排列——中介数+1（这里是递增进位制数字的加法，区别于一般的十进制加法），跳回步骤（2）
如果已经输出所有的排列——结束
算法正确性证明
对于一个给定的中介数，对应于一个唯一的排列，这里排列和中介数的一一对应性的证明我们不做讨论。m位(m为正整数)递增递减进位制数字有(m+1)！个，因此对于一个m位的中介数可能的取值有(m+1)！。又因为中介数与排列一一对应，所以由m位的中介数可以求出(m+1)！个排列。一个m位的中介数对应m+1个数字，m+1个不同元素的全排列有(m+1)！个。因此递增进位制法可以生成全排列。
递减进位制法
该方法与递增进位制法的原理相似，不同的是它定义的“递减进位制数”是数字的进制随着位数的递增而递减。这种进制一般最左边的进制是2，次左边的进制是3。其余原理与递增进位制法基本相同。
算法步骤
在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。递减进位制数字是指数字的进制随着数字位置的不同递减。
定义: i的右边比i小的数字的个数, 则() ↓为递减进位制法中定义的中介数，这里的中介数是递减进位制数字，递减进位制数（a2 a3 a4 a5 a6 a7 a8 a9）为：最低位逢9进1，次低位逢8进1……。例如，839647521对应的中介数为(12224376)↓。由中介数求排列时，从大到小根据从大到小求出n,n-1,…,2,1的位置——从右向左将第+1个空填上i，剩下的最后一个空位填上1。因此根据“原排列”→“原中介数”→“新中介数”→”新排列“，在这样的定义下，可以求出下一个排列。所以根据递减进位制法生成全排列步骤如下：
#初始化中介数（每一位都为0）
#根据中介数求出对应的排列，输出排列
#如果没有输出所有的排列——中介数+1（这里是递减进位制数字的加法，区别于一般的十进制加法和递增进位制数字加法），跳回步骤(2)
#如果已经输出所有的排列——结束
算法正确性证明
对于一个给定的中介数，对应于一个唯一的排列，这里排列和中介数的一一对应性的证明我们不做讨论。m位(m为正整数)递减递减进位制数字有(m+1)！个，因此对于一个m位的中介数可能的取值有(m+1)！。又因为中介数与排列一一对应，所以由m位的中介数可以求出(m+1)！个排列。一个m位的中介数对应m+1个数字，m+1个不同元素的全排列有(m+1)！个。因此递减进位制法可以生成全排列。
实例：给定一个排列求后面或者前面的某个排列
由“原排列”→“原中介数”→“新中介数”→“新排列”的方式求解：
按照以上字典序法、递增进位制数、递减进位制数法和邻位对换法四种算法，分别求出 83674521 之前第 2015 个排列。
参考资料
评论 (0)