关于前端SKU算法的一知半解

· 2021-09-13 11:08:33 ·

SKU 是什么？

存货单位（英语：stock keeping unit，SKU/ˌɛsˌkeɪˈjuː/）[1]，也翻译为库存单元，是一个会计学名词，定义为库存管理中的最小可用单元，例如纺织品中一个SKU通常表示规格、颜色、款式，而在连锁零售门店中有时称单品为一个SKU。最小库存管理单元可以区分不同商品销售的最小单元，是科学管理商品的采购、销售、物流和财务管理以及POS和MIS系统的数据统计的需求，通常对应一个管理信息系统的编码。 --维基百科

应用场景

在线商城购物选择属性

举个🌰

现有以下规格

const type = ["男裤", "女裤"]
const color = ["黑色", "白色"]
const size = ["S","L"]

那么可以得到的所有SKU为：

[
  ["男裤", "黑色", "S"],
  ["男裤", "黑色", "L"],
  ["男裤", "白色", "S"],
  ["男裤", "白色", "L"],
  ["女裤", "黑色", "S"],
  ["女裤", "黑色", "L"],
  ["女裤", "白色", "S"],
  ["女裤", "白色", "L"],
]

手动穷举可以写出来了，怎么用代码翻译一下呢？

SKU 组合实现思路

笛卡尔积

首先让我们来看看笛卡尔积的描述

笛卡尔乘积是指在数学中，两个[集合] X 和 Y 的笛卡尔积，又称 [ 直积 ] ，表示为 X × Y，第一个对象是 X 的成员而第二个对象是 Y 的所有可能 [ 有序对 ] 的其中一个成员 --百度百科

假设集合 A = { a, b }，集合 B = { 0, 1, 2 }，则两个集合的笛卡尔积为 { ( a, 0 ), ( a, 1 ), ( a, 2), ( b, 0), ( b, 1), ( b, 2) }

上面的例子的笛卡尔积画出思维导图就是以下这种：

通过上面的思维导图，可以看出这种规格组合是一个经典的排列组合，去组合每一个规格值得到最终 SKU。

那么让我们来进行代码实现，看看代码如何实现笛卡尔积。

实现代码

 /**
 * 笛卡尔积组装
 * @param {Array} list
 * @returns []
 */
function descartes(list) {
  return list.reduce(
    // flatMap: [[1], [2], [3]].flatMap(c => c) 返回： [1,2,3]
    (a, b) => a.flatMap(
      // a是prevItem, b是currentItem
      x => b.map(
        // [] => ['男裤'] => ['男裤', '黑色'] => ['男裤', '黑色', 'S']
        y => [...x, y]
      )
    ),
    [[]] 
  )
}

让我们看看实际的输入输出和调用结果。

那么这个经典的排列组合问题就这样解决啦。接下来，让我们再看看，如何在商品购买中，去处理商品多规格选择。

商品多规格选择

开始前回顾下使用场景

我们可以看到，当我们选择了一个属性之后，就需要通过程序计算去筛选处理剩余可选的组合，将不可选属性值置灰disabled掉

那么我们的实现思路就有了：

通过后端接口返回数据生成所有SKU组合
初始化所有可选的组合（也可以说是有货的组合）
每选择一个属性后，都根据已选属性项的值过滤出剩余可选的组合
最终在全部规格选择完成后，得到选中的 SKU

商品多规格选择实现思路

说实现思路之前先来回顾一下大学里面学的图和邻接矩阵

什么是图

图是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。

图是由"顶点"和连接这些顶点的"边"组成。

需要注意的是，图的顶点集合不能为空，但边的集合可以为空。当边的集合为空时，图就是无向的。边在连接顶点时无需区分方向。当需要区分方向的时候，图就是有向的。

另外还有有权图和无权图，本文用不到，过~

那么我们需要用到的是无向图，什么是无向图呢，就像这样：

两个顶点之间如果有连线，则表示这两个顶点是互通的。

看到这里你们肯定想说，废话了那么多，好像跟我们要解决的问题没关系啊。

大家不妨想一下：用户在选择属性的时候，肯定是没有先后顺序的，假设我们现在把每个属性看作是无向图的一个顶点的话，我们可以根据这些单项规格的组合规格，就可以画出一个像上图一样的无向图。那图是画出来了，咋用代码表示？？？？？那就请出邻接矩阵吧

邻接矩阵

邻接矩阵其实是线性代数里面的概念，你们肯定都不会陌生。

图的邻接矩阵存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息，一个二维数组存储图中的边的信息，这个二维数组就称之为邻接矩阵。

如果两个顶点互通（有连线），那么它们对应下标的值则为 1，否则为 0。

让我们继续前面的🌰 数据来看

规格

const type = ["男裤", "女裤"]
const color = ["黑色", "白色"]
const size = ["S","L"]

假设总 SKU 的库存值为下面示例，可选为有库存，不可选为某项规格无库存

[
  ["男裤", "黑色", "S"], = 6 // S 无号
  ["男裤", "黑色", "L"], = 10
  ["男裤", "白色", "S"], // S 无号
  ["男裤", "白色", "L"],
  ["女裤", "黑色", "S"], // S 无号
  ["女裤", "黑色", "L"],
  ["女裤", "白色", "S"], // S 无号
  ["女裤", "白色", "L"],
]

那么根据邻接矩阵思想，可以得到结果图：

从图中可以看出，SKU 中每两规格都可选择，那么相对的标志值为 1，否则为 0，当整条规格选中都是 1，才会使整条 SKU 链路可选。

思路是有了，代码去实现？

实现方式那肯定就多可去了~

介绍一下使用集合的实现方式

计算思路

集合

高中过去好多年了，难免忘记，这里通过集合说明图一起回顾下集合的定义

图片来自百度百科~

想起集合，那么计算思路算是有了，这边我们需要用集合相等的情况，去处理 SKU 和规格值的计算。

实现思路：

第一步，将所有规格处理为质数
1. 为什么要使用质数？
  1. 因为质数只能被1和自身整除
  2. 在集合计算中，如果集合可以整除某个质数，那么这个质数对应的规格一定在这个集合中
2. 实现思路：从第一个质数开始递增，每次递增后判断是否是质数，并进行存储。最终可以得到一个与sku相对应的质数。
第二步：将所有可用的SKU对应的规格质数合集计算
1. 实现思路：将处理过的质数和可选的SKU进行筛选，得到可选的每个SKU的质数的集合值
第三步：将可选中的SKU和规格质数对应，进行初始化处理
1. 实现思路：通过可选SKU合集，反向遍历出每个规格，得出可选的规格质数
第四步：选择
1. 实现思路：每次选择时，先得到已选规格质数的合集，添加此次选择的规格质数，再次使用可选SKU集合反向遍历，重新得到后续可选规格质数
第五步：移除规格
1. 实现思路：当取消一个已选中项时，从已选规格质数集合中，移除次规格质数，再次使用可选SKU集合反向遍历，重新得到后续可选规格质数

假设一个集合 A{a, b, c} 和另外一个集合 B{a, e}，如何快速判断 B 是否是 A 的子集。这个问题比较简单的方法是用 B 中所有元素依次和 A 中的元素进行比较，对于集合中的元素，每个元素值都是唯一的。通过这样的特性，我们可以把所有字母转换为一个质数，那么 集合 A 可以表示为集合元素(质数)**的积，B 同样，**B 是否是 A 的子集，这个只需要将 B 除以 A，看看是否可以整除，如果可以那么说明，B 是 A 的子集。
- A {男裤，黑色，S} => A{ 1, 2, 3 }
- B { 男裤，黑色 } => B {1, 2}
- 1*2*3 = 6 1 * 2 = 2 6 / 2 = 3 说明 B是A的子集
那么根据邻接矩阵思路，整条 SKU 都会有一个集合值，集合值由所有涉及规格对应乘积得到的结果，在选择规格过程中，每次选择去根据集合值去反向整除规格对应值去判断是否是子集，是否为 1。
现在根据乘法算法，有了以上的分析，我们可以整理下算法过程：
- 数据预处理，把所有需要处理的规格内容一一对应一个不重复的质数，把 ITEM 组合转换为每个质数的积
- 根据用户已经选择的 ITEM 进行扫描所有的 ITEM，如果 ITEM 已经被选中，则退出。如果没有，则和所有已经选择的 ITEM 进行相乘 (因为一个组合不可能出现两个类目相同的 ITEM，所以选中的 ITEM 需要去掉和当前匹配的 ITEM 在同一个类目中的 ITEM ) ，这个乘积就是上文中的集合 B
- 把集合 B 依次和 SKU 组合构成的积 (相当于上文中的集合 A) 进行相除，比较，如果整除，则退出，当前匹配的 SKU 可以被选中，如果一直到最后还没有匹配上，则当前匹配的 SKU 不可被选中。

我们通过集合的思想，就可以轻松实现了。看看代码吧。

整体代码

本地预览

参考文献

上述集合计算思路借鉴文献，详情见链接。
另一种正则匹配实现思路文献借鉴，详情见链接。
邻接矩阵思路借鉴文献，详情见链接。
图论基础