题目描述
高中的时候数学课上(或者小学奥数)学的排列组合,大家还记得吗?排列比较简单,就不提了。那么,组合
怎么用程序来实现呢?
比如箩筐里有6个标了号的苹果,1 2 3 4 5 6,从里面取出3个苹果,都有什么取法呢?
/*
* arr 一筐苹果的数组,比如['1', '2', '3', '4', '5', '6']
* num 选出几个
*/
function getCombination(arr, num) {
//写啊写啊
}
getCombination(6, 3)
// 输出 [1, 2, 3], [1, 2, 4], [2, 3, 6]...这样的
// 按照公式计算应该有20种组合方式
答案解析
针对这道题目,组内同事分别给出了以下的解法。
1. 暴力破解法
let ary = ['1', '2', '3', '4', '5', '6'];
let num = 3;
function matrixMultiply(arr1, arr2) {
let arr1L = arr1.length;
let arr2L = arr2.length;
let product = [];
for (let i = 0; i < arr1L; i++) {
let temp1 = Array.isArray(arr1[i]) ? arr1[i] : [arr1[i]];
for (let j = 0; j < arr2L; j++) {
let temp2 = [arr2[j]];
if (temp1[temp1.length - 1] < temp2[temp2.length - 1]) {
product.push(temp1.concat(temp2));
}
}
}
return product;
}
function getCombination(arr, num) {
let indexArr = arr.map((item, index) => index);
let result = indexArr;
if (num === 1) {
return arr;
} else {
for (let i = 1; i < num; i++) {
result = matrixMultiply(result, indexArr.slice(i));
}
return result.map(item => item.map(index => arr[index]));
}
}
2. 标准答案
let ary = ['1', '2', '3', '4', '5', '6'];
let num = 3;
function getCombination(arr, num) {
var r=[]; // 结果数组
(function f(t,a,n){
// 递归出口
if (n == 0) return r.push(t);
// 循环递归,遍历各种可能
for (var i=0,l=a.length; i<=l-n; i++) {
f(t.concat(a[i]), a.slice(i+1), n-1);
}
})([],arr,num);
return r;
}
3. 高性能解法
let ary = ['1', '2', '3', '4', '5', '6'];
let num = 3;
function getCombination(arr, num) {
let result = [];
let item = [];
// index 表示数组开始下标
// repeat表示fun被调用的次数
function fun(index, repeat) {
let end = ary.length - num + index;
for(var i = index + repeat; i <= end; i++) {
item[index] = ary[i];
index++;
if(index < num) {
fun(index, repeat);
repeat++
index--;
} else {
result.push([].concat(item));
index--;
}
}
}
fun(0, 0)
console.log(result);
}
getCombination(ary, num);
第二种解法和第三种解法,思想大致一样。下面主要针对第三种解法进行解析。
这道题有以下几个关键点:
num
是一个变量,所以for
循环的嵌套层级是无法确定的,所以只能采用递归,num
就是嵌套的层级深度;- 按照人类的正常思维,6个里面选3个,一般第一个元素可以选1-4个中的一个,如果第一个元素选择第一个1,第二个元素就只能在2-5中选,如果第二个为2,那么第三个元素从3-6中选择。大致的组合过程如下表所示:
第1个(区间1-4) | 第2个(区间2-5) | 第3个(区间3-6) |
---|---|---|
1 | 2 | 3,4,5,6 |
1 | 3 | 4,5,6 |
1 | 4 | 5,6 |
1 | 5 | 6 |
2 | 3 | 4,5,6 |
2 | 4 | 5,6 |
2 | 5 | 6 |
- 需要通过变量
repeat
和index
控制区间的起始点,end控制区间的终点。
总结
通过产生长度为200的一个数组进行测试,比较三种方法的性能,得出第三种方法性能比较高,原因是数组API,concat、slice会降低代码性能。测试代码如下:
// 产生随机数组
let ary = [];
for (var i = 0; i < 200; i++) {
ary[i] = Math.random();
}
let start = Date.now();
getCombination(ary, num);
let end = Date.now();
console.log(end - start);
推荐阅读
- 【第22题】理解 JS 模块化
- 【深入vue】为什么Vue3.0不再使用defineProperty实现数据监听?
- 抛弃jenkins,如何用node从零搭建自动化部署管理平台
- 前端部署演化史
- 支持跨时区、兼容本地时间不准且不依赖后端接口的倒计时
- 解读HTTP/2与HTTP/3 的新特性(推荐)
关注我
扫一扫 关注我的公众号【前端名狮】,更多精彩内容陪伴你!