团队一个小伙伴儿提了个问题，二维数组交叉组合分组算法怎么实现？一听这怎么着复杂度都是一个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. 动态规划算法优化策略

2 comments