根据N种规格中的M种规格值生成的全部规格组合的一种算法

时间:2023-03-09 15:06:46
根据N种规格中的M种规格值生成的全部规格组合的一种算法

近来在开发SKU模块的时候,遇到这样一个需求,某种商品有N(用未知数N来表示是因为规格的数组由用户制定且随时可以编辑的,所以对程序来说,它是一个未知数)类规格,每一类规格又有M个规格值,各种规格值的组合便是一个型号,比如说,颜色是商品规格的一类,可能的值有红、黄、绿、蓝,而尺码是另一类规格,可能的取值有L、M。那它们的规格组合数为:4*2 = 8,如果再另一类规格是版型,分别为修身和宽松,那就有4 * 2 * 2 = 16种组合了。怎样简单高效地求出这些组合呢?

这类问题首先考虑的方法是用递归,但返回之间并没有相互依赖的关系,到底什么时候结束是个问题,用嵌套的循环又会由于数组的维度及深度不得而知而变得困难重重,后来,想到了一种很可能并非性能最优,但简单直观的方法,写在这里与大家分享一下,如果你有更好的算法,请不吝赐教,小弟感激不尽。

刚开始的时候想到要从多个数组中依次抽取一个元素出来,感觉去进行深度遍历相当复杂,后来换了一种思路,其实每次只要把两个数组合并起来,然后把这两个数组合并的结果再与下个数组进行合并,最终,就能得出逐个抽取一个元素来进行组合的结果。这跟算组合总数的思路是一样的,也就是2*4*3,先是求出2*4=8,再用8*3=24;这样,24种组合的结果就得了,下面是JS代码,供大家参考一下,我知道这肯定并非最佳算法,所以,再次希望有其它解决办法的朋友赐教。

function generateTrRow(specItemList){
var specValueList = [];
for(var i in specItemList){
var s = specItemList[i];
var arrValue = s.value.split(',');
specValueList.push(arrValue);
}
var arrGroup = [], tempGroup = [];
if(specValueList.length > ){
var firstSpecValueList = specValueList[];
for(var i in firstSpecValueList){
tempGroup.push([firstSpecValueList[i]]);
}
specValueList.splice(, );
arrGroup = generateGroup(specValueList, tempGroup);
}
}
/**
* 生成规格值组合的方法
*/
function generateGroup(arrSpecValueList, tempGroup){
for(var i in arrSpecValueList){
var s = arrSpecValueList[i];
var newTempGroup = [];
for(var j in tempGroup){
for(var k in s){
var tempOne = [];
for(var x in tempGroup[j]){
tempOne.push(tempGroup[j][x]);
}
tempOne.push(s[k]);
newTempGroup.push(tempOne);
}
}
if(newTempGroup.length > ){
tempGroup = newTempGroup;
}
}
return tempGroup;
}

  

其中generateTrRow方法是我生成表格中的行用到的,它主导把数组合并后删除已合并的数组,下面的generateGroup方法则是执行把两个数组合并的请求。