全排列生成算法
此条目包含指南或教学内容。 (2017年6月20日) |
全排列的生成算法[1]方法是将给定的序列中所有可能的全排列无重复无遗漏地枚举出来。此处全排列的定义是：从n个元素中取出m个元素进行排列，当n=m时这个排列被称为全排列。
字典序、邻位对换法、循环左移法、循环右移法、递增进位制法、递减进位制法都是常见的全排列生成算法。
字典序法
编辑字典序，就是将元素按照字典的顺序（a-z, 1-9）进行排列。以字典的顺序作为比较的依据，可以比较出两个串的大小。比如 "1" < "13"<"14"<"153"， 就是按每个数字位逐个比较的结果。对于一个串“123456789”， 可以知道最小的串是“123456789”，而最大的串“987654321”。这样针对这个串以字典序法生成全排列生成全排列，就是依次生成“123456789”->“123456798”->......->"987654312"->"987654321"这样的串。字典序法要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。[2]
算法步骤
编辑设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|Pi<Pi+1，i>j}
- 在 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[i+1]) {
j = i;
break;
}
}
// 此时已经是最大序了
if (j == -1) {
System.out.println("end");
return false;
}
// j后边比j位置大的最小的一个位置
int k = -1;
int min = Integer.MAX_VALUE;
for (int i=j; i<array.length; i++) {
if (array[i] > array[j] && array[i] <= min) { // 这里要找到最后一个，否则对于存在相同元素的集合会出现错误。如：0122
min = array[i];
k = i;
}
}
// 交换j和k的值
int tmp = array[j];
array[j] = array[k];
array[k] = tmp;
// 对j后边的序列进行反转
int left = j+1;
int right = array.length - 1;
while (left < right) {
int t = array[left];
array[left] = array[right];
array[right] = t;
left ++;
right --;
}
for (int i : array) {
System.out.print(i + ", ");
}
System.out.println();
return true;
}
插入法
编辑如果已知n-1个元素的排列，将n插入到排列的不同位置，就得到了n个元素的排列。用这种方法可以产生出任意n个元素的排列。这个方法有一个缺点：为了产生n个元素的排列，我们必须知道并存储所有n-1个元素的排列，然后才能产生出所有n阶排列。[3]
邻位对换法
编辑该算法由Johnson-Trotter首先提出，是一个能快速生成全排列的算法。它的下一个全排列总是上一个全排列对换某相邻两位得到的。
算法步骤
编辑- 初始化n个元素的排列为123……n，并规定其元素的方向都是向左的，元素的方向用一个数组b来表示，当b[i]=0，表示第i个元素的方向向左，当b[i]=1时表示第i个元素的方向向右。
- 在排列中找出排列中所有处于活动状态的元素中最大的一个。
- 将它与它所指向相邻元素交换。
- 把排列中大于上面找出的处在活动状态的最大元素大的其他元素的方向倒转。
算法正确性证明
编辑假设其对n个元素能生成全排列，只需要证明其对n+1个元素，也能生成全排列，对于新进来的元素，将其认为值最大，插入最右方，每次从右移到左，或者改变方向后从左移到右就可以认为对于一个排列从不同位置插入生成一个新的排列，而对于n个元素是全排列的，因此对于n+1个元素也是全排列的，因此邻位对换法能生成全排列。
递增进位制法
编辑这个算法是基于序列的递增进位制数[3]。递增进位制数是指数字的进制随着位数的递增而递增。一般情况下，数字最右边的进制是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，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。递减进位制数字是指数字的进制随着数字位置的不同递减。[3]
定义: 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 个排列。
| 中介数 | 2015中介数 | 新中介数 | 新排序 | 备注 |
|---|---|---|---|---|
| 7244221 | 243321 | 7000300 | 81237456 | 字典序法 |
| 7442221 | 243321 | 7153300 | 86451273 | 递增法 |
| 1222447 | 10567 | 1211450 | 37624518 | 递减法 |
| 1012120 | 10567 | 1001121 | 48673251 | 邻位对换 |