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

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

安利一个我自己开发的 vue-sku-form 组件，它主要是应用在电商系统后台里，对 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 的场景。一般情况下，后台会通过接口提供给我们两组数据，分别是 属性集 和 数据集 ，这里我就用两组固定数据模拟一下：

// 属性集
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 ，如果将它转为数组，就是：

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

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

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

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

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

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

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

['', '', '', '']

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

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

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

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

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

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

我们可以分别去验证一下

// 源数据 ['黑', '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']

实现代码如下（非原创）：

// 从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;电信 得到这样的一组数据了

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

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

['', '', '']
['黑', '', '']
['', '16G', '']
['', '', '移动']
['黑', '16G', '']
['黑', '', '移动']
['', '16G', '移动']
['黑', '16G', '移动']

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

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

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

// 最大值
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 的算法还是有很多优化的地方，当然一定也有还没考虑到的问题。本文抛砖引玉，希望能给同行一些思路。

SKU 表单配置组件

2020/9/3 更新

这篇文章是从前台的角度是实现 SKU 组合查询，数据都是写死的，而在实际项目中，数据是由后台配置完成，这部分的配置也有一定的实现难度，于是我就开发了一个通用组件 vue-sku-form ，用于配置 SKU 表单。

同时也提供了一份基于 Vue 的前台实现。

参考

• 用例子理解排列组合及基本公式如何计算
• 淘宝SKU组合查询算法实现
• Sku 多维属性状态判断算法