您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
排列(排列五走势图带连线)
递归,排列,组合排列(排列五走势图带连线)
发布时间:2016-12-08加入收藏来源:互联网点击:
很多朋友想了解关于排列的一些资料信息,下面是小编整理的与排列相关的内容分享给大家,一起来看看吧。
作者 | 码海
责编 | Elle
前言上一篇「一文学会递归解题」一文颇受大家好评,各大号纷纷转载,让笔者颇感欣慰,不过笔者注意到后台有读者有如下反馈
确实,相信很多人(包括我自己)都有类似的感慨,对某个知识点,看确实是看懂了,但如果真的再用同样的套路再去解一些带有同样解题思路,但稍加变形的题,往往会束手无策。对这种情况有啥好的解决办法吗?
除了勤加练习,还有一良策!
鲁迅先生说:如果学习算法,最好一段时间内只刷某种算法思想或某种数据结构的题,啥意思呢?比如说你上次学了递归,那就持续找递归的题来刷,学了链表,这段时间就专门刷链表的题,千万不可今天刷递归,明天刷动态规划,后天又开始学习贪心算法。。。新手最怕的就是以为自己懂了,浅尝辄止,这是新手的大忌!一定要对同一类型的题穷追猛打,形成肌肉记忆,这样之后再碰到同一类型的题就会条件反射地一看:哦,这题用 xxx 思想应该可以靠谱。
言归正转,排列组合是面试中的热门考点因为看似简单的排列组合可以有挺多的变形,根据变形,难度可以逐渐递增,而且排列组合本身有挺多的解法,能很好地区分一个侯选者的算法水平,排列组合如果用递归挺不容易理解的(反正笔者一开始看了好几遍代码愣是没看懂),之后我会教大家如何用一种非常简单地方式来理解排列组合的递归,这也是写本文的根本目的
接下来我们看看如何用 「递归四步曲」来解排列组合,本文会从以下几个方面来讲解排列组合
什么是排列
排列的常用解法
什么是组合
组合递归解法
面试中排列组合的一些变形
什么是排列排列的定义:从n个不同元素中,任取 m (m≤n,m与n均为自然数,下同)个不同的元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,当 n = m 时,我们称这样的排列为全排列
看到这个公式,大家是不是回忆起了高中的排列公式啦
我们重新温习一下,以 1, 2, 3 这三个数字的全排列有多少种呢。
第一位我们可以选择 3 个数字,由于第二位不能与第一位相等,所以第二位只能选 2 个数字,第一,第二位既然选完了,那么第三位就只有 1 个数字可选了,所以总共有 3 x 2 x 1 = 6 种排列。
既然知道了什么是全排列,那我们来看看怎么用程序来打印全排列的所有情况:求 数字 1 到 n (n 10) 的全排列
排列的常用解法这道题如果暂时没什么头绪,我们看看能否用最简单的方式来实现全排列,什么是最简单的方式,暴力穷举法!
暴力穷举法大家仔细看上文中 1,2 ,3 的全排列,就是把所有情况全部列举出来了,所以我们用暴力穷举法怎么解呢,对每一位的每种情况都遍历出来组成所有的排列,再剔除重复的排列,就是我们要的全排列了
/*** 求数字第 1 到 n 的全排列*/public void permutation(int n) {for(int i = 1; i n + 1; i ++) {for(int j = 1; j n + 1; j ++) {for(int k = 1; k n + 1; k ++) {if (i != j i != k j != k) {System.out.println(i + j + k);}}}}}时间复杂度是多少呢,做了三次循环,很显然是
很多人一看时间复杂度这么高,多数都会嗤之以鼻,但是要我说,得看场景,就这题来说用暴力穷举法完全没问题,n 最大才 9 啊,总共也才循环了 9^3 = 729 次,这对现在的计算机能来说简单不值一提,就这种场景来说,其实用暴力穷举法完全可行!
这里说句题外话,我们在学习的过程中一定要视场景选择合适的技术方案,有句话说:过早的能优化是万恶之源,说的就是这个道理,这就好比,一个初创公司,dau 不过千,却要搞分布式,中间件,一个 mysql 表,记录不过一万,却要搞分库分表。。。这就闹笑话了,记住没有最牛逼的技术,只有最合适的技术!能解决当前实际问题的技术,就是好技术!
递归解题这是笔者写此文的根本目的!就是为了讲清楚怎么用递归来更好地理解排列组合!因为我发现很多网友都觉得排列组合的递归解法实在不能 Get 到点上, 当初笔者也是看了好几遍代码才勉强理解,不过过了一段时间再看又忘了,后来根据笔者悟出的一套递归四步曲来理解,容易多了,现与各位分享!仔细看好啦
我们先来观察一下规律,看下怎样才能找出排列是否符合递归的条件,因为如前文 所述,必须要找出题目是否能用递归才能再用递归四步曲来解题
乍一看确实看不出什么所以然出来,那我们假设第一个数字已经选中了(假定为1),问题是不是转化为只求后面三位数的全排列了,发现没有,此时全排列从前面 n 位数的全排列转化成了求之后 n-1 位数的全排列了,问题从 n 变成了 n-1,规模变小了!而且变小的子问题与原问题具有相同的解决思路,都是从求某位开始的全排列!符合递归的条件!
既然我们发现排列符合递归条件,那我们就可以用递归四步曲来解了
1、定义函数的功能要求数字 1 到 n 的全排列,我们定义以下函数的功能为求从 k 位开始的全排列,数组 arr 存的是参与全排列的 1 到 n 这些数字
public void permutation(int arr[], k) {}2、寻找递推公式注意上面形成递归的条件:第一个数字已经选中了!那第一位被选中有哪些情况呢,显然有以下几种情况
即在第一位上把所有的数字都选一遍,怎么做才能把所有的数字都在第一位上都选一遍呢,把第一位与其他 n-1 位数分别交换即可(注意每一次交换前都要保证是原始顺序),如下
画外音:第一步交换自己其实就是保持不变,因为我们要保证在第一位所有数字都能取到,如果移除了这一步,则第一位少了数字 1 ,全排列就漏了
这样我们就把第一位的所有数字都选了遍,之后只要对剩余的 n-1 位数做全排列即可(即调用第一步的函数),切忌再对 n-1 再做展开,只要我们发现递推关系就行了,千万不要陷入层层展开子问题的陷阱当中去!注意要从函数的功能来理解,因为问题与子问题具有相同的解决思路,所以第 1 步定义的函数对子问题(求 n-1 ,n-2 ... 的全排列)同样适用!
那递归的终止条件是什么呢 ,显然是从 n 缩小到对最后一位的全排列(此时 k 指向 arr 的最后一个元素)
于是我们可以得出递推关系为:permutation(int arr[], k) = 选中第k位(将第k位与之后的 n- k 位分别交换) + permutation(int arr[], k+1)
3、将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中,补充后的函数如下
/**** @param arr 代表全排列数字组成的数组* @param k 代表第几位*/public void permutation(int[] arr, int k) {// 当 k 指向最后一个元素时,递归终止,打印此时的排列排列if (k == arr.length - 1) {System.out.println(Arrays.toString(arr));} else {for (int i = k; i arr.length; i++) {// 将 k 与之后的元素 i 依次交换,然后可以认为选中了第 k 位swap(arr, k, i);// 第 k 位选择完成后,求剩余元素的全排列permutation(arr, k+1);// 这一步很关键:将 k 与 i 换回来,保证是初始的顺序swap(arr, k, i);}}}public static void swap (int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}下一篇:返回列表
相关链接 |
||
网友回复(共有 0 条回复) |