【第23题】排列组合

611 阅读3分钟

题目描述

高中的时候数学课上(或者小学奥数)学的排列组合,大家还记得吗?排列比较简单,就不提了。那么,组合怎么用程序来实现呢?

比如箩筐里有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);

第二种解法和第三种解法,思想大致一样。下面主要针对第三种解法进行解析。

这道题有以下几个关键点:

  1. num 是一个变量,所以for循环的嵌套层级是无法确定的,所以只能采用递归,num 就是嵌套的层级深度;
  2. 按照人类的正常思维,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
  1. 需要通过变量repeatindex控制区间的起始点,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);

推荐阅读

  1. 【第22题】理解 JS 模块化
  2. 【深入vue】为什么Vue3.0不再使用defineProperty实现数据监听?
  3. 抛弃jenkins,如何用node从零搭建自动化部署管理平台
  4. 前端部署演化史
  5. 支持跨时区、兼容本地时间不准且不依赖后端接口的倒计时
  6. 解读HTTP/2与HTTP/3 的新特性(推荐)

关注我

扫一扫 关注我的公众号【前端名狮】,更多精彩内容陪伴你!