团队一个小伙伴儿提了个问题,二维数组交叉组合分组算法怎么实现?一听这怎么着复杂度都是一个O(n^n)的算法实现了,什么业务场景需要这么折腾?

了解了下,背景是这样:一个用户可能有N个标签组,每个标签组有不同的标签属性;需求是,需要根据这N个标签组的属性组合生成用户组。

把业务抽象之后,也可以这么描述:

给定一个不定长的二维数组,例如:[['A1', 'A2', 'A3'], ['B1', 'B2']]
实现一个方法输出:[['A1', 'B1'],['A1', 'B2'],['A2', 'B1'],['A2', 'B2'],['A3', 'B1'],['A3', 'B2']]

这确实就不可避免的需要n的n方算法实现了。

场景一:矩阵的行列式展开(又叫笛卡尔乘积)

以上场景类似矩阵的行列式展开算法实现,实现细节如下;但涉及核心线性代数基础(比如矩阵的连乘实现)需再探究。

/**
 * 二维数组交叉组合分组算法实现
 * 
 * @param {Array} arr 
 */
function determinant(arr){
  const result = [];

  const totalLength = arr.length;
  const currentFlag = new Array(totalLength).fill(0)

  getItems(0);

  return result;

  function getItems(curIndex){
    const nextIndex = curIndex + 1;

    // 必须在根节点执行回调逻辑
    if (curIndex === totalLength) {
      result.push(currentFlag.reduce((sum, item, index)=>{
        sum.push(arr[index][item]);
        return sum;
      }, []));
    }

    if (nextIndex > totalLength) return;

    for (let i = 0; i < arr[curIndex].length; i++){
      currentFlag[curIndex] = i;
      // 递归调用
      getItems(nextIndex);
    }

  }
}

场景二:单一数组全排列

联想到另外一个场景,题设是这样:

假设现在有N张发票,总面额是11,000元。
实现一个算法:将这N张发票尽可能分给10个人,使每个人的发票总面额大于1000元,而且余下来的发票总面额尽可能最大

这是一个可以动态规划解决的场景之一,这里仅实现了一个数组全排列的方案:

    /**
     * 排列组合算法:传入一个数组,计算所有可能的排列组合,在回调中逐一执行
     * @param {Array}   arr      默认数组
     * @param {Function} 
     */
    function Permutation(arr, callback) {
      var result = [];

      times(arr, result);

      function times(arr, result) {
        var length = arr.length;
        if (length == 0) {
          callback && callback(result)
          return;
        }
        for (var i = 0; i < length; i++) {
          var newArr = arr.slice();
          newArr.splice(i, 1);

          var newResult = [].concat(result, arr[i])
          times(newArr, newResult)
        }
      }
    }

具体的实现可以移步:http://wilee.me/demo/grouping.html

[TODO]

  1. 矩阵连乘实现
  2. 动态规划算法优化策略

1 comments