扑通扑通's blog

购物车SKU组合算法

• 标签: js性能思考 sku 算法

前言

这两天深刻领悟js中对象属性访问方便性，所以当涉及到要循环的时候总是要考虑下，如何避免循环，最佳的做法就是变化成对象属性访问。
接下来来看下手机端下单sku的做法。

条件

属性1：A B
属性2：a b c
属性2：黑色
有这样一个对象，里面存储了现有组合的信息

1
2
3
4
5
6
var data = {
    "A;a;黑色":{price:20,count:10},
    "A;b;黑色":{price:22,count:12},
    "B;b;黑色":{price:24,count:14},
    "B;c;黑色":{price:25,count:16}
};

由于手机端选择sku的时候，每点击一个按钮的时候都要像用户展示当前已选择的规格中的价格范围和库存，比如，我点击A的时候，products里是没有A和c的搭配的，所以c按钮会变灰色，剩下的价格范围是20-22，库存是10+12=22。

这样的结果需要怎么操作呢？

先确认需求：A;a;黑色 —-> A,a,黑色,Aa,A黑色,a黑色,Aa黑色 —-> 一共七种可能 —-> 这就涉及到了组合的思想

把所有的结果放在SKUResult数组里面，当你选择了A,黑色的时候，组成key值(“A;黑色”)，这时候要想拿到price,count信息，只需要找SKUResult[“A;黑色”]就可以拿到啦【这样子做就可以避免一次次的循环】

不可避免的是，我每次点击一个规格的时候，在所有规格(去除自己和同属性)中循环，判断当前是否是没有组合的(也就是没有的禁用掉变灰)

组合算法

本算法序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标代表的数被选中，为0则没选中。
首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为”01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组下标的m-n的位置，即count个“1”全部移动到最右端时，就得到了最后一个组合。 

1
2
3
4
5
6
7
8
9
10
11
例如求5中选3的组合：    
1   1   1   0   0   //1,2,3    
1   1   0   1   0   //1,2,4    
1   0   1   1   0   //1,3,4    
0   1   1   1   0   //2,3,4    
1   1   0   0   1   //1,2,5    
1   0   1   0   1   //1,3,5    
0   1   1   0   1   //2,3,5    
1   0   0   1   1   //1,4,5    
0   1   0   1   1   //2,4,5    
0   0   1   1   1   //3,4,5

刚开始循环的时候，合适的i前面有leftCnt个’1’,需要把leftCnt个’1’往左边移动
arr[0] ~ arr[leftCnt-1] —-> 全部置为1
arr[leftCnt] ~ arr[i-1] —-> 全部置为0

思路的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 获得从m中取n的所有组合
 * C m n排列组合
 */
function getFlagArrs(m, n) {
    if(!n || n < 1) {
        return [];
    }
    var resultArrs = []
        ,flagArr = []
        ,isEnd = false
        ,i
        ,j
        ,leftCnt
    ;
    for (i = 0; i < m; i++) {
        flagArr[i] = i < n ? 1 : 0;
    }
    resultArrs.push(flagArr);
    while (!isEnd) {
        leftCnt = 0;//记录合适的'10'组合前面的'1'的个数
        for (i = 0; i < m - 1; i++) {
            if (flagArr[i] == 1 && flagArr[i+1] == 0) {
                flagArr[i] = 0;
                flagArr[i+1] = 1;
                //将符合情况的10组合前面所有的1往左移动
                for(j = 0; j < i; j++) {
                    flagArr[j] = j < leftCnt ? 1 : 0;
                } 
                var aTmp = flagArr.concat();
                resultArrs.push(aTmp);
                //如果从倒数第N个开始选取组成字符串，这个字符串没有0的话，循环遍历结束
                if(aTmp.slice(-n).join("").indexOf('0') == -1) {
                    isEnd = true;
                }
            break;
            }
            leftCnt += flagArr[i] == 1 ? 1 : 0;
        }
    }
    return resultArrs;
}