0%

电商平台商品 SKU 组合查询算法实现

在大部分前端开发同学的日常工作中,很少会遇到算法问题,不得不说是种遗憾。但随着前端能处理的事务越来越多,多多少少也会遇到一些算法问题,就比如今天我打算讨论的这个问题——SKU组合查询。

什么是 SKU

我们看下维基百科是怎么解释的:

最小库存管理单元(Stock Keeping Unit, SKU)是一个会计学名词,定义为库存管理中的最小可用单元,例如纺织品中一个SKU通常表示规格、颜色、款式,而在连锁零售门店中有时称单品为一个 SKU 。

 
官方的解释可能有点晦涩,我举个例子,假设有一个手机,信息如下表格所示:

颜色 内存 容量 电池 摄像头
白色 4G 16G 2200mAh 1600万像素
黑色 6G 32G 2800mAh
银色 64G 3200mAh
红色

这款手机分别提供了颜色、内存、容量、电池、摄像头 5 种可选属性,而表格中加粗部分组合在一起,就形成了一个 SKU :

黑色 + 4G + 32G + 3200mAh + 1600万像素

问题描述

还是拿手机举例,假设现在这台手机只有颜色和内存 2 种可选属性,颜色只有黑色和白色,内存只有 4G 和 6G 。我们把属性组合一下,列举出所有的 SKU ,同时也显示出库存数量和价格:

颜色 内存 库存 价格
黑色 4G 0 1799
黑色 6G 10 1999
白色 4G 10 1899
白色 6G 10 2099

可以看到这组数据里 黑色 4G 已经没有存货,而 黑色 6G白色 4G白色 6G 分别还有 10 个货源在。那么,当用户对商品进行选择的时候,如果首先选择 黑色 ,对应的 4G 应该显示为不可选择状态,因为 黑色 4G 是没有货的。同样,如果先选择了 4G ,对应的 黑色 也应该显示为不可选择状态,因为 黑色 4G 还是没有货的。

解决办法

场景还原

要解决这个问题,我们先模拟一个商品购买选择 SKU 的场景。一般情况下,后台会通过接口提供给我们两组数据,分别是 属性集数据集 ,这里我就用两组固定数据模拟一下:

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
// 属性集
var key = [
{name: '颜色', item: ['黑', '金', '白']},
{name: '内存', item: ['16G', '32G']},
{name: '运营商', item: ['电信', '移动', '联通']}
];

// 数据集
var sku = {
'黑;16G;电信': {price: 100, count: 10},
'黑;16G;移动': {price: 101, count: 11},
'黑;16G;联通': {price: 102, count: 0},
'黑;32G;电信': {price: 103, count: 13},
'黑;32G;移动': {price: 104, count: 14},
'黑;32G;联通': {price: 105, count: 0},
'金;16G;电信': {price: 106, count: 16},
'金;16G;移动': {price: 107, count: 17},
'金;16G;联通': {price: 108, count: 18},
'金;32G;电信': {price: 109, count: 0},
'金;32G;移动': {price: 110, count: 20},
'金;32G;联通': {price: 111, count: 21},
'白;16G;电信': {price: 112, count: 0},
'白;16G;移动': {price: 113, count: 23},
'白;16G;联通': {price: 114, count: 24},
'白;32G;电信': {price: 115, count: 0},
'白;32G;移动': {price: 116, count: 26},
'白;32G;联通': {price: 117, count: 27}
};

有了这两组数据,就可以实现最基本的 SKU 选择功能了。用 属性集 去渲染 DOM,当用户选择好 SKU 后,程序将用户选择的属性拼接成一个 sku 字符串,比如 金;16G;电信 ,再根据这个字符串去 数据集 里获取库存和价格,演示如下:

上面这个演示有个最大的问题就是,必须把每个属性都选择后,才能获取到对应的库存和价格,如果没有选择完整,就无法获取对应的数据。

原因也很简单,因为 数据集 里没有提供嘛。比如我只选择了 ,那么当前拼接出来的 sku 则是 白;; ,自然找不到这条 sku 的相关数据。那要怎么解决呢?那就把 数据集 加工一下嘛。

数据加工

我拿 数据集 里某一条 sku 举例,比如 黑;16G;电信 ,将这个 sku 进行更小的拆分组合,希望得到以下的结果:

  • ;;
  • 黑;;
  • ;16G;
  • ;;电信
  • 黑;16G;
  • 黑;;电信
  • ;16G;电信
  • 黑;16G;电信

这里会涉及到本文中最核心的一个算法,让我们再仔细看下举例的这个 sku ,如果将它转为数组,就是:

1
['黑', '16G', '电信']

如果把最终希望得到的结果也转为数组,那就是:

1
2
3
4
5
6
7
8
['', '', '']
['黑', '', '']
['', '16G', '']
['', '', '电信']
['黑', '16G', '']
['黑', '', '电信']
['', '16G', '电信']
['黑', '16G', '电信']

然后仔细观察一下这组数据,看出些端倪了么?

没看出来?没关系,我们把这个 sku 再增加一个属性,如果数组是这样子的:

1
['黑', '16G', '电信', '2800mAh']

那最终希望得到的结果也会有变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
['', '', '', '']

['黑', '', '', '']
['', '16G', '', '']
['', '', '电信', '']
['', '', '', '2800mAh']

['黑', '16G', '', '']
['黑', '', '电信', '']
['黑', '', '', '2800mAh']
['', '16G', '电信', '']
['', '16G', '', '2800mAh']
['', '', '电信', '2800mAh']

['黑', '16G', '电信', '']
['黑', '16G', '', '2800mAh']
['黑', '', '电信', '2800mAh']
['', '16G', '电信', '2800mAh']

['黑', '16G', '电信', '2800mAh']

相信有人已经看出来了,这里需要实现的一个算法就是:

从 m 个不同元素中取出 n 个元素的组合数

我们可以分别去验证一下

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
// 源数据 ['黑', '16G', '电信', '2800mAh']

// 从 4 个元素中取 0 个元素的组合
['', '', '', '']

// 从 4 个元素中取 1 个元素的组合
['黑', '', '', '']
['', '16G', '', '']
['', '', '电信', '']
['', '', '', '2800mAh']

// 从 4 个元素中取 2 个元素的组合
['黑', '16G', '', '']
['黑', '', '电信', '']
['黑', '', '', '2800mAh']
['', '16G', '电信', '']
['', '16G', '', '2800mAh']
['', '', '电信', '2800mAh']

//从 4 个元素中取 3 个元素的组合
['黑', '16G', '电信', '']
['黑', '16G', '', '2800mAh']
['黑', '', '电信', '2800mAh']
['', '16G', '电信', '2800mAh']

//从 4 个元素中取 4 个元素的组合
['黑', '16G', '电信', '2800mAh']

实现代码如下(非原创):

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
// 从m中取n的所有组合
function getFlagArrs(m, n) {
var flagArrs = [],
flagArr = [],
isEnd = false;
for(var i = 0; i < m; i++){
flagArr[i] = i < n ? 1 : 0;
}
flagArrs.push(flagArr.concat());
// 当n不等于0并且m大于n的时候进入
if(n && m > n){
while(!isEnd){
var leftCnt = 0;
for(var i = 0; i < m - 1; i++){
if (flagArr[i] == 1 && flagArr[i + 1] == 0){
for(var j = 0; j < i; j++){
flagArr[j] = j < leftCnt ? 1 : 0;
}
flagArr[i] = 0;
flagArr[i + 1] = 1;
var aTmp = flagArr.concat();
flagArrs.push(aTmp);
if(aTmp.slice(-n).join('').indexOf('0') == -1){
isEnd = true;
}
break;
}
flagArr[i] == 1 && leftCnt++;
}
}
}
return flagArrs;
}

这个方法在调用后返回的 flagArrs 并不是最终所需要的业务数据,而是返回一组这样的数据

这时候需要用源数据,也就是 ['黑', '16G', '电信', '2800mAh'] 依次循环填坑,将数组中为 1 的部分替换掉,0 的部分则留空,这样就能得到我们需要的数据了。

解决到这一步后,后面的工作就相对轻松了。

我们已经能根据 黑;16G;电信 得到这样的一组数据了

1
2
3
4
5
6
7
8
['', '', '']
['黑', '', '']
['', '16G', '']
['', '', '电信']
['黑', '16G', '']
['黑', '', '电信']
['', '16G', '电信']
['黑', '16G', '电信']

但这数据里并没有存放库存以及价格信息,这时候我们先观察一下数据,一个 sku 就能得到一组这样的数据,换一个 sku 一样还是能得到一组类似的数据,比如换成 黑;16G;移动 就会得到

1
2
3
4
5
6
7
8
['', '', '']
['黑', '', '']
['', '16G', '']
['', '', '移动']
['黑', '16G', '']
['黑', '', '移动']
['', '16G', '移动']
['黑', '16G', '移动']

发现了么?其中有几个数据是一样的,比如都有出现 ['黑', '', ''] ['', '16G', ''] ['黑', '16G', ''] ……

我只需把数据一样的库存进行累加,同时把价格存到一个数组里。这样把 数据集 里所有的 sku 都循环一遍后,对应的库存数就统计出来了。比如每个 sku 都会出现 ['', '', ''] ,那累计得出的自然也就是该商品的总库存数量;再比如 sku 里有出现过 ['黑', '', ''] ,最终累计得出的就是该商品颜色为黑色的库存数量。

至于价格,因为每次循环,价格都被保存到与 sku 相对应的一个数组里,比如 ['', '', ''] 就会保存 数据集 所有 sku 的价格, ['黑', '', ''] 则会保存与黑色相关的所有价格。如果要获取价格,通过 js 的 Math 对象能很轻松的获取数组里的最大值和最小值。

1
2
3
4
// 最大值
Math.max.apply(Math, Array);
// 最小值
Math.min.apply(Math, Array);

至此,我们已经能实现用户选择一个或多个属性时,均能展示当前的库存和价格信息,演示如下:

关联 SKU 验证

先恭喜你离最终我们所希望达到的效果,只差一步了。

好,回归问题,我们希望当用户点击属性选择的时候,程序能去验证一些可能点击的属性,提前把 0 库存的属性设为禁止选中状态。我把这里的操作分为两种情况,一种是当用户只差一个属性没选的时候,另一种是当用户所有属性都选择的时候。

当用户只差一个属性没选

这种情况下,只需将已选中的属性依次和未选中属性里的值拼接,如果拼接出来的 sku 库存为 0 ,则将对应未选中属性的值设为禁止状态。如果没理解,下面我用张表格具体举例,加粗表示已经选中的属性。

颜色 内存 容量
白色 4G 16G
黑色 6G 32G
银色 64G
红色

上面表示颜色和内存都已选好,程序要做的事就是循环容量属性里的值,然后把颜色和内存里已选择的值组成 sku 去检查库存。这里会验证 3 组 sku :

  • 黑色;4G;16G
  • 黑色;4G;32G
  • 黑色;4G;64G

如果验证出 黑色;4G;32G 的库存是 0 ,那就把 32G 设为禁止选择。

当用户所有属性都选择

这种情况下,则需要将每组属性里未被选中的值和其它已选中的属性拼接,将拼接出来的 sku 进行验证。还是用张表格来举例吧。

颜色 内存 容量
白色 4G 16G
黑色 6G 32G
银色 64G
红色

第一步,先将颜色里未选择的值去组成 sku :

  • 白色;4G;64G
  • 银色;4G;64G
  • 红色;4G;64G

如果验证出 银色;4G;64G 的库存是 0 ,那就把 银色 设为禁止选择。

第二步,再将内存里未选择的值去组成 sku :

  • 黑色;6G;64G

如果验证出 黑色;6G;64G 的库存是 0 ,那就把 6G 设为禁止选择。

最后一步,将容量里未选择的值去组成 sku :

  • 黑色;4G;16G
  • 黑色;4G;32G

如果验证出 黑色;4G;32G 的库存是 0 ,那就把 32G 设为禁止选择。

按照这个思路,我们最终的演示也出来了

总结

整个功能实现的思路相对还是比较清晰的,比较费时的就是两个算法的实现。

第一个算法,将 数据集 进行更小的拆分组合时候,我最开始的想法是用 属性集 去进行组合和递归,但一直无法得出最终想要的结果,于是才改从 数据集 下手。

第二个算法,点击验证 SKU 其实还可以继续优化,我举个例子:

颜色 内存 容量
白色 4G 16G
黑色 6G 32G
银色 64G
红色

如上表格,如果 黑色;4G;16G黑色;6G;16G 的库存都是 0 ,那么在用户选中 黑色 的时候,则应该把 16G 设为禁止选中状态。但基于我的算法方案,当用户只选中 黑色 的时候,却不属于两种情况当中的任何一种,则无法进行验证。

关于 SKU 的算法还是有很多优化的地方,当然一定也有还没考虑到的问题。本文抛砖引玉,希望能给同行一些思路。

参考