无限个数排列组合算法的高效实现与应用（任意集合笛卡尔乘积非递归实现）

1.业务场景描述

在做电商的时候，添加商品时，需要为每个商品添加sku。而sku是由多个属性值组合而成，我们现在需要有一个功能，当用户选择完属性值以后，自动生成所有属性值的组合，组合规则：每一种属性值只能组合一次。需求如下：

2.算法的分析与设计

我们可以手动的枚举出匹配过程，再来分析找出规律从而设计出合适的算法。

2.1分析

已知属性值矩阵如下：

我们手动枚举出所有匹配

2.2寻找规律

我们发现有 m * n 不规则矩阵，它总共拥有组合的个数 为每一行列数之积的总和，在我们的例子中就是2*3*2*3=36种。而第一行1 2的组合结果是 1 * 18 ，这里的*是指重复次数，2*18。而第二行除了和第一行有相同规律外，最外层又重复了2次，这种规律让我们看到了算法设计的思路。

2.3算法设计

通过数学归纳法我们得出以下计算公式：

组合的每一列计算：(第i列 * (row+1)的总组合数)) * (总组合数/每一列生成的组合总数之和)

通过这种算法，我们最终会得到一个每行是组合列的组合数，然后我们再通过行列组合转化成我们最终的组合排列。

3.代码实现

 function converCombineForCols(combine_cols, delimiter='-') {
        var combine_row_cols = [];
        for (var i = 0; i < combine_cols[0].length; i++) {
            var result = '';
            for (var j = 0; j < combine_cols.length; j++) {
                result += combine_cols[j][i] + delimiter;
            }
            combine_row_cols.push(result.slice(0, -1));
        }
        return combine_row_cols;
    }

    function makeCombineByCols(attr_checked_map) {
        var combine_cols = [];
        var combine_total = 1;
        for (var i = 0; i < attr_checked_map.length; i++) {
            combine_total *= attr_checked_map[i].checked.length;
        }
        for (var i = 0; i < attr_checked_map.length; i++) {
            var str = '';
            for (var j = 0; j < attr_checked_map[i].checked.length; j++) {
                var repeatForCol = getRepeatCountForCol(i, attr_checked_map);
                var repeatTotal = combine_total / (repeatForCol * attr_checked_map[i].checked.length);
                str += (attr_checked_map[i].checked[j] + ',').repeat(repeatForCol);
            }
            str = str.repeat(repeatTotal);
            combine_cols.push(str.slice(0, -1).split(','));
        }
        return combine_cols;
    }

    function getRepeatCountForCol(current_row, attr_checked_map) {
        var repeat = 1;
        if (current_row === attr_checked_map.length - 1) {
            return repeat;
        }
        for (var i = current_row + 1; i < attr_checked_map.length; i++) {
            repeat *= attr_checked_map[i].checked.length;
        }
        return repeat;
    }

    var attr_checked_map = [{checked:[1,2]},{checked:[4,5,6]}, {checked:[1,2]}, {checked:[1,2,3]}];
    var combine_cols = makeCombineByCols(attr_checked_map);
    var combine_row_cols = converCombineForCols(combine_cols);

    console.log('--------------combine_cols-----------------');
    console.log(combine_cols);
    console.log('--------------combine_col_rows-------------');
    console.log(combine_row_cols);

4.后续补充

这个问题我之后在群里请教过，其本质就是任意集合笛卡尔乘积的实现，另外给出群里讨论的结果算法分别用js和php实现。

 function makeSku()
    {
        var result = arguments[0];
        for(var i = 1; i < arguments.length; i++) {
            var temp = [];
            for(var j = 0; j < result.length; j++) {
                for(var k = 0; k < arguments[i].length; k++) {
                    temp.push(result[j] + '-' + arguments[i][k]);
                }
            }
            result = temp;
        }
        return result;
    }

function makeSku(...$arr)
{
    $result = $arr[0];

    for ($i = 1; $i < count($arr); ++$i) {
        $temp = [];
        foreach ($result as $res) {
            foreach ($arr[$i] as $val) {
                $temp[] = $res . '-' . $val;
            }
        }
        $result = $temp;
    }

    return $result;
}

laravel collection 也提供了笛卡儿积的实现

$collection = collect([1, 2]);

$matrix = $collection->crossJoin(['a', 'b']);

$matrix->all();

其实现的方式如下：

 public static function crossJoin(...$arrays)
    {
        $results = [[]];

        foreach ($arrays as $index => $array) {
            $append = [];

            foreach ($results as $product) {
                foreach ($array as $item) {
                    $product[$index] = $item;

                    $append[] = $product;
                }
            }

            $results = $append;
        }

        return $results;
    }

笔者的算法，从时间复杂度来讲，是臃肿低效的。但是，我还是想把我分析问题的过程分享给大家，希望大家能够得到启发。

如无特殊说明，文章均为本站原创，转载请注明出处。如发现有什么不对的地方，希望得到您的指点。