江苏龙网

  1. 主页 > 生活百科 > >

一文学会排列组合 排列组合公式( 三 )


【一文学会排列组合 排列组合公式】字典序法
除了递归解法，还有一种常用的解法：字典排序法啥叫字典排序法？
举个例子：1 2 3 这三位数字的全排列如下
1 2 3 ，1 3 2 ，2 1 3 ，2 3 1 ，3 1 2 ，3 2 1
以上排列满足从小到大依次递增，按这种方法排列的算法就叫字典排序法 。
所以我们只要从排列的最小值开端,依次按从小到大依次递增的次序找寻下一个全排列的数字即可，直到最大值！就能找到所有全排列 。
假设我们定义了一个叫 nextPermutation 的函数,依据字典排序法，则从最小值 123 开端，连续调用这个函数即可求出所有全排列的组合,如图示
那么这个函数该怎么实现呢
有 4 个步骤
1、从右到左（从个位数往高位数）寻找第一个左邻小于右邻的数，如果找不到解释此时的数字为全排列的最大值
2、再从右往左找第一个比第一步找出的数更大的数
3、交流上面两个步骤中的数
4、假设第一步寻找的数对应的地位为 i，则将 i+1至最后一个元素从小到大进行排序，排好序后，此时的数字就是我们要找的那个排列
举个例子: 假设当前给的数字是 124653，按这四个步骤来看如何寻找这个数按字典排序法的下一个全排列数字
1、从右到左（从个位数往高位数）寻找第一个左邻小于右邻的数，显然是 4
124653
2、再从右往左找第一个比第一步找出的数（4）更大的数, 显然是 5
124653
3、交流上面两个步骤中的数,即交流 4，5，此时数字为 125643
4、 125643 中的 643 从小到大进行排序，显然应当为 125346,这一步的排序我们用了快排
整体思路还是很清楚的，如果不太清晰，建议大家多看几遍 。
思路清晰了，代码写起来就快了，直接贴上按以上步骤来实现的代码吧，注释写得很详细了，大家可以对比着看
/**
*
* @param arr 当前排列
* @return boolean 如果还有下一个全排列数，则返回 true, 否则返回 false
*/
public booleannext_permutation(int[] arr) {
int beforeIndex = 0; //记载从右到左寻找第一个左邻小于右邻的数对应的索引
int currentIndex;
boolean isAllReverse = true; // 是否存在从右到左第一个左邻小于右邻的数对应的索引
// 1. 从右到左（从个位数往高位数）寻找第一个左邻小于右邻的数
for(currentIndex = arr.length - 1; currentIndex > 0; --currentIndex){
beforeIndex = currentIndex - 1;
if(arr[beforeIndex] < arr[currentIndex]){
isAllReverse = false;
break;
}
}
//如果不存在，解释这个数已经是字典排序法里的最大值，此时已经找到所有的全排列了,直接打印即可
if(isAllReverse){
return false;
} else {
// 2. 再从右往左找第一个比第一步找出的数更大的数的索引
int firstLargeIndex = 0;
for(firstLargeIndex = arr.length - 1; firstLargeIndex > beforeIndex; --firstLargeIndex) {
if (arr[firstLargeIndex] > arr[beforeIndex]) {
break;
}
}
// 3. 交流 上述 1, 2 两个步骤中得出的两个数
swap(arr, beforeIndex, firstLargeIndex);
// 4. 对 beforeIndex 之后的数进行排序，这里用了快排
quicksort(arr, beforeIndex + 1, arr.length);
return true;
}
资源网}
public void swap (int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
注：以上第四步的排序用到了快排（quicksort），限于篇幅关系没有贴出快排的完全代码，如果不懂得快排，建议大家网上查查看，这里不做详细展开
那 next_permutation 的时光庞杂度是多少呢，从以上的步骤中其实可以看到是第四步做快排时的时光庞杂度，即 O(nlogn) 。
next_permutation 我们写好了，接下来要寻找全排列就容易了，思路如下
1、 首先对参与全排列的数字数组作排序，保证初始的排列数字必定是最小的即如果起始的 int arr = {4,3,2,1} 经过快排后会变成 {1,2,3,4}
2、连续调用定义好的 next_permutation 函数，直到最大值
public void permutation(int[] arr) {
// 1、 快排，保证 arr 里的元素是从小到大的
quicksort(arr);
// 2、连续调用定义好的 next_permutation 函数，直到最大值
while(next_permutation(arr)) {
System.out.println(Arrays.toString(array));
}
}
可以看到如果定义好了 next_permutation，在算全排列还是很简略的，那用字典序法的时光和空间庞杂度是多少呢由于全程只用了arr 数组，空间庞杂度显示是 O(n)而时光庞杂度显然是第一步快排的空间庞杂度 + 连续做 next_permutation 盘算的时光庞杂度 。


推荐阅读


上一篇：教你把二、十六进制数转换成十进制数 十六进制转十进制

下一篇：同比增长和环比增长的区别 环比和同比是什么意思