一文学会排列组合
前言
上一篇「一文学会递归解题」一文颇受大家好评，各大号纷纷转载，让笔者颇感欣慰，不过笔者注意到后台有读者有如下反馈
除了勤加练习，还有一良策！
鲁迅先生说：如果学习算法，最好一段时间内只刷某种算法思想或某种数据结构的题，啥意思呢?比如说你上次学了递归，那就持续找递归的题来刷，学了链表，这段时间就专门刷链表的题，千万不可今天刷递归，明天刷动态规划，后天又开始学习贪心算法。。。新手最怕的就是以为自己懂了，浅尝辄止，这是新手的大忌！一定要对同一类型的题穷追猛打，形成肌肉记忆，这样之后再碰到同一类型的题就会条件反射地一看:哦,这题用 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);
}
}
}
}
}
递归解题
public void permutation(int arr[], k) {
}
2、寻找递推公式注意上面形成递归的条件：第一个数字已经选中了！那第一位被选中有哪些情况呢,显然有以下几种情况
/**
*
* @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;
}
我看网上有不少人对最后一步（如图示）不理解
所以最后一个 swap 要做的事情就是每次交换第一个数字与后面被选中的那个数，做完之后元素的全排列之后，要把数字交换回来，以保证接下来再用第一位与其他位的数字进行交换前是原始的序列，这样才能保证第一位数字与之后的 n-1 个元素依次交换之后都是不重复的。
字典序法
/**
*
* @param arr 当前排列
* @return boolean 如果还有下一个全排列数，则返回 true, 否则返回 false
*/
public boolean next_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），限于篇幅关系没有贴出快排的完整代码，如果不了解快排，建议大家网上查查看，这里不做详细展开
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 计算的时间复杂度。
什么是组合
组合（combination）是一个数学名词。一般地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。
-
如果第一个元素选中，则要从之后的 n-1 个元素中选择 m-1 个元素 -
如果第一个元素未被选中，则需要从之后的 n-1 个元素选择 m 个元素
public static final int COMBINATION_CNT = 5; // 组合中需要被选中的个数
public static void combination(int[] arr, int k, int[] select) {
}
combination(arr, k,m) = (选中 k 位置的元素 +combination(arr, k+1) ) + (不选中 k 位置的元素 +combination(arr, k+1) )
-
一个是被选中的元素已经等于我们要选择的组合个数了 -
一个是 k （开始选取的数组索引） 超出数组范围了。
public static final int COMBINATION_CNT = 5; // 组合中需要被选中的个数
public static void combination(int[] arr, int k, int[] select) {
// 终止条件1：开始选取的数组索引 超出数组范围了
if (k >= arr.length) {
return;
}
int selectNum = selectedNum(select);
// 终止条件2：选中的元素已经等于我们要选择的数组个数了
if (selectNum == COMBINATION_CNT) {
for (int j = 0; j < select.length; j++) {
if (select[j] == 1) {
System.out.print(arr[j]);
}
}
System.out.print("\n");
} else {
// 第 k 位被选中
select[k] = 1;
combination(arr, k+1, select);
// 第 k 位未被选中
select[k] = 0;
// 则从第 k+1 位选择 COMBINATION_CNT - selectNum 个元素
combination(arr, k+1, select);
}
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9};
int[] select = {0,0,0,0,0,0,0,0,0};
// 一开始从 0 开始选 组合数
combination(arr, 0, select);
}
4、求时间/空间复杂度空间复杂度：由于我们用了一个辅助数组 select, 所以空间复杂度是 O(n)时间复杂度：可以看到 f(n) = 2f(n-1)，所以时间复杂度是O(2^n),显然是指数级别的
面试中排列组合的一些变形
-
在全排列时参与排列的数字都是不相同的， 如果有相同的数字（比如参与排序的是 1， 1，2，3），在使用递归进行解题时，需要进行怎样的改造； -
在组合中 ，我们的题目是从 n 中选出 m 个数，如果要选出所有组合呢，比如给定 1，2，3，所有的组合是1, 2, 3, 12, 13, 23, 123, 此时以上的递归解法又该怎么改造。
声明：本文为作者投稿，版权归作者个人所有。
热 文 推 荐
☞骗了马云 10 亿被骂 4 年后，院士王坚留下 4 条人生启示
登录查看更多
相关内容
Arxiv
4+阅读 · 2018年8月29日
Arxiv
4+阅读 · 2018年4月26日
Arxiv
4+阅读 · 2018年1月16日
相关VIP内容
相关资讯
相关论文
Arxiv
4+阅读 · 2018年8月29日
Arxiv
4+阅读 · 2018年4月26日
Arxiv
4+阅读 · 2018年1月16日
微信扫码咨询专知VIP会员