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;
}
笔者的算法,从时间复杂度来讲,是臃肿低效的。但是,我还是想把我分析问题的过程分享给大家,希望大家能够得到启发。
如无特殊说明,文章均为本站原创,转载请注明出处。如发现有什么不对的地方,希望得到您的指点。