您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
排列(排列五走势图带连线)
递归,排列,组合排列(排列五走势图带连线)
发布时间:2016-12-08加入收藏来源:互联网点击:
我看网上有不少人对最后一步(如图示)不理解
回过头去看上面的递归过程图中我们特意强调了注意每一次交换时都要保证是原始顺序
所以最后一个 swap 要做的事情就是每次交换第一个数字与后面被选中的那个数,做完之后元素的全排列之后,要把数字交换回来,以保证接下来再用第一位与其他位的数字进行交换前是原始的序列,这样才能保证第一位数字与之后的 n-1 个元素依次交换之后都是不重复的。
注定一定要从函数的功能去理解递归,全排列的函数从功能上可以这么理解,选中第 k 位 + 计算之后的 n-k 位的全排序, 而且由于是递归,之后的 n-k 位也可以重复调用同样的函数持续求解!
4、求时间/空间复杂度由于我们只用了一个数组 arr,所以空间复杂度显然是 O(n),那时间复杂度呢,仔细看上面的编码可以很明显地看出计算 n 的全排列需要做 n 次循环,循环里是要做 2 次交换(由于是固定数字,可以认为是常数 C ),还有一次对之后 n-1 次元素的全排列所以 f(n) = n * (C + f(n-1)),C是常数可以忽略,所以
f(n) = n * f(n-1) = n * (n-1) * f(n-2) = n!,所以时间复杂度是 O(n!),注意不可能有比这个更好的时间复杂度了!因为全排列的组合本身就有 n! 次,再怎么优化都肯定会有这么多次
在 n 较大的情况下显然是不可接受的,所以我们要想办法进行优化
字典序法除了递归解法,还有一种常用的解法:字典排序法啥叫字典排序法?
举个例子: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 计算的时间复杂度。
快排的时间复杂度为 O(nlogn),而 next_permutation 由于要计算 n! 次, 且根据以上分析我们已经知道了 next_permutation 的时间复杂度是 O(nlogn), 所以整体的时间复杂度是
O(nlog) + O(n! * nlogn) = O(n! * nlogn)。
看起来字典序法比递归的时间复杂度更高,所以我们应该使用倾向于使用递归吗?这里注意: 递归的实现是通过调用函数本身,函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括:局部变量、形参、调用函数地址、返回值。那么,如果递归调用N次,就要分配N局部变量、N形参、N调用函数地址、N返回值,这势必是影响效率的,同时,这也是内存溢出的原因,因为积累了大量的中间变量无法释放。
所以在时间复杂度差不多的情况下,优化选择非递归的实现方式
什么是组合看完了排列,我们来看看组合,首先我们还是先看看组合的定义
组合(combination)是一个数学名词。一般地,从n个不同的元素中,任取m(m≤n)个元素为一组,叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。
假设有数字1, 2, 3, 4, 要从中选择 2 个元素,共有多少种组合呢
共有 6 种
排列与组合最主要的区别就是排列是有序的,而组合是无序的,12 和 21 对组合来说是一样的
现在我们来看看如果从 n 个元素中选出 m 的组合共有几种,之前详细地讲解了如何用递归解排列,相信大家应该对组合怎么使用递归应该有一个比较清晰的思路。
下一篇:返回列表
相关链接 |
||
网友回复(共有 0 条回复) |