相信大家看到这张图片就知道我们这篇文章要讲什么了，没错就是-商品多规格选择的解法。
近来在掘金上面看见大家都在研究商品多规格选择的问题，例如晨曦大佬的前端电商sku的全排列算法很难吗？学会这个套路，彻底掌握排列组合。在这篇文章里面，大佬写明了如何实现sku的全排列，思路非常的棒，但是并没有紧贴业务场景。真正的业务场景是，我们要根据用户每一次选择的规格，找出剩下可选的规格和不可选的规格，表现在前端页面上：就是将不可选的规格置灰，也就是如下效果（可以点击这里查看最终效果）：
那么今天我们就来讲讲这个问题的一个解决方法，要讲明白很难，但是我相信你看了这篇文章之后，sku就再也难不倒你了。
什么是sku
在介绍具体解法之前，我们先来介绍一下什么是sku?sku是会计学中的一个名词，被称作库存单元。说人话？简单来讲就是，我们上图中每一个单规格选项，例如深空灰色、64G，都是一个规格(sku)。商品和sku属于一对多的关系，也就是我们可以选择多个sku来确定到某个具体的商品：
业务场景
可以这么说，只要是做电商类相关的产品，比如购物APP、购物网站等等，都会遇到这么一个场景，每个商品对应着多个规格，用户可以根据不同的规格组合，选择出自己想要的产品。我们自己在生活中也会经常用到这个功能，然而就是这样一个简单的功能，却难倒了很多小伙伴。
笔者也是一样，刚开始遇到这个场景，笔者觉得应该一个下午就能搞定，完美收工，奈何还是太过于年轻，搞了差不多两天，在网上查阅了很多相关的文章和资料，但是不得其解，最后没有办法，只能硬着头皮采用暴力求解（也就是不断循环）的方法来解决的，时间复杂度贼高，达到了O(m*n)也就是O(n2),这种实现方法其实也不是不行（能跑就行），对吧。但是后来笔者发现，当一个商品的规格非常非常多、并且用户的设备性能不是那么好的情况下，那么这种实现方式就会导致运行时间过长，表现在页面上就是：当用户点击了一个规格，会有明显的卡顿，那怎么行，客户都流失了，老板还怎么买法拉利？所以笔者又开始了研究。
图
一个偶然的机会，笔者在逛知乎的时候，看到了有人在讨论图，这个数据结构，突然灵光一现，貌似咱们的多规格选择也可以用图来作求解方法，后来一尝试，还真的可行。而且时间复杂度只有O(n)，简直完美。所以我们下面来介绍一下图，什么是图？相信大学学过数据结构与算法的同学都应该知道，不过应该已经忘得一干二净了。
什么是图
图其实是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系：
图通常有如下分类:
分为有向图和无向图
分为有权图和无权图
好了知道这两个概念就差不多了,当然如果想了解更多图多概念，请看这里
那么我们需要用到的是无向图，什么是无向图呢，就像这样：
两个顶点之间如果有连线，则表示这两个顶点是互通的。小伙伴们看到这里可能会懵逼了，说了这么多，好像跟我们要解决的问题没关系啊。小伙伴们现在想一想：用户在选择规格的时候，肯定是没有先后顺序的，假设我们现在把每种规格看作是无向图的一个顶点的话，我们可以根据这些单项规格的组合规格，就可以画出一个像上图一样的无向图。
邻接矩阵
假设我们已经画出了如上的无向图，那么我们如何将这个图用咱们的代码来表示呢？这里就用到了邻接矩阵
邻接矩阵其实是《线性代数》里面的概念，相信很多小伙伴都不会陌生，我们在代码中，表示它的方法是用一个nxn的二维数组来抽象邻接矩阵。让我们来把上面这个无向图用邻接矩阵(二维数组)表示出来：
很显然，如果两个顶点互通（有连线），那么它们对应下标的值则为1，否则为0。
好了，下面开始逐步都是高能，请小伙伴们认真观看。
假设现在我们有如下规格列表：
specList:[{title:"颜色",list:["红色","紫色"]},{title:"套餐",list:["套餐一","套餐二"]},{title:"内存",list:["64G","18G","56G"]},];
可供选择的规格组合有：
specCombinationList:[{id:"1",specs:["紫色","套餐一","64G"]},{id:"",specs:["紫色","套餐一","18G"]},{id:"",specs:["紫色","套餐二","18G"]},{id:"4",specs:["红色","套餐二","56G"]}],
首先，我们根据specList知道：我们有“颜色”、“套餐”、“内存”三种规格类别。分别有红色、紫色、套餐一、套餐二、64G、18G、56G这些单项规格。每个单项规格作为一个顶点，所以就有如下顶点：
然后我们根据specCombinationList，我们可以知道，哪些规格的组合是可选的。好了我们要开始画图了。
根据{id:"1",specs:["紫色","套餐一","64G"]},我们可以画出：
接下来依葫芦画瓢：我们可以根据specCombinationList剩下的数据画出如下的图：
好了，我们已经根据specCombinationList(也就是可选规格组合)将我们的规格无向图画完了。现在我们来模拟一下用户的选择:
specCombinationList:[{id:"1",specs:["紫色","套餐一","64G"]},{id:"",specs:["紫色","套餐一","18G"]},{id:"",specs:["紫色","套餐二","18G"]},{id:"4",specs:["红色","套餐二","56G"]}],
假设用户先选择了紫色、根据specCombinationList,我们发现套餐一、套餐二、64G、18G是可选的，这个时候我们发现一个问题：显然跟紫色同级的红色其实也是可选的。所以这个图其实我们还没有画完。所以相同类型的规格，只要是在可选规格里面的，他们其实是应该连接起来的：
好了，无向图画好了，现在我们将它映射到邻接矩阵上面（这一步强烈建议小伙伴们拿出纸笔来一起画一画）：
到了这一步，恭喜你，你已经懂了一大半了。
好了，到这我们就可以公布最终结论了：
当用户初次进入该页面时，所有的规格均可选：
当用户选择了某个顶点后，当前顶点所有可选项均被找出（即是当前顶点所在列值为1的顶点）：
选取多个顶点时，可选项是各个顶点邻接点的交集：（即是选中顶点所在列的交集）
代码实现
说真的，我觉得小伙伴们看明白了我上面这些讲解，相信你已经完全懂了该如何实现“多规格选择”算法了。不过有句话叫做：光说不练假把式！那下面我们就一起来捋一捋，用代码如何实现吧，笔者这里用的前端框架是act，明白思路了，用什么框架都一样的哦。
这里先说下思路：
1、根据规格列表（specList）创建邻接矩阵（数组）
、根据可选规格组合(specCombinationList)填写顶点的值
、获得所有可选顶点，然后根据可选顶点填写同级顶点的值
创建邻接矩阵
首先，我们需要提供一个类来创建邻接矩阵。一个邻接矩阵，首先需要传入一个顶点数组：vertex,需要一个用来装邻接矩阵的数组：adjoinArray。刚刚我们上面说到了，这个类还必须提供计算并集和交集的方法：
exporttypeAdjoinType=Arraystring;exportdefaultclassAdjoinMatrix{vertex:AdjoinType;//顶点数组quantity:number;//矩阵长度adjoinArray:Arraynumber;//矩阵数组constructor(vertx:AdjoinType){this.vertex=vertx;this.quantity=this.vertex.length;this.adjoinArray=[];this.init();}//初始化数组init(){this.adjoinArray=Array(this.quantity*this.quantity).fill(0);}/**
paramidstring*paramsidesArraystring*传入一个顶点，和当前顶点可达的顶点数组，将对应位置置为1*/setAdjoinVertexs(id:string,sides:AdjoinType){constpIndex=this.vertex.indexOf(id);sides.forEach((item)={constindex=this.vertex.indexOf(item);this.adjoinArray[pIndex*this.quantity+index]=1;});}/**paramidstring*传入顶点的值，获取该顶点的列*/getVertexCol(id:string){constindex=this.vertex.indexOf(id);constcol:Arraynumber=[];this.vertex.forEach((item,pIndex)={col.push(this.adjoinArray[index+this.quantity*pIndex]);});turncol;}/**paramparamsArraystring*传入一个顶点数组，求出该数组所有顶点的列的合*/getColSum(params:AdjoinType){constparamsVertex=params.map((id)=this.getVertexCol(id));constparamsVertexSum:Arraynumber=[];this.vertex.forEach((item,index)={constrowtotal=paramsVertex.map((value)=value[index]).duce((total,curnt)={total+=curnt0;turntotal;},0);paramsVertexSum.push(rowtotal);});turnparamsVertexSum;}/**
paramparamsArraystring*传入一个顶点数组，求出并集*/getCollection(params:AdjoinType){constparamsColSum=this.getColSum(params);letcollections:AdjoinType=[];paramsColSum.forEach((item,index)={if(itemthis.vertex[index])collections.push(this.vertex[index]);});turncollections;}/**paramparamsArraystring*传入一个顶点数组，求出交集*/getUnions(params:AdjoinType){constparamsColSum=this.getColSum(params);letunions:AdjoinType=[];paramsColSum.forEach((item,index)={if(item=params.lengththis.vertex[index])unions.push(this.vertex[index]);});turnunions;}}有了这个类，接下来可以创建一个专门用于生成商品多规格选择的类，它继承于AdjoinMatrix。
创建多规格选择邻接矩阵
我们这个多规格选择的邻接矩阵，需要提供一个查询可选顶点的方法：getSpecscOptions
importAdjoinMatrixfrom"./adjoin-martix";import{AdjoinType}from"./adjoin-martix";import{SpecCategoryType,CommoditySpecsType}from"../dux/ducer/spec-ducer";exportdefaultclassSpecAdjoinMatrixextendsAdjoinMatrix{specList:ArrayCommoditySpecsType;specCombinationList:ArraySpecCategoryType;constructor(specList:ArrayCommoditySpecsType,specCombinationList:ArraySpecCategoryType){super(specList.duce((total:AdjoinType,curnt)=[...total,...curnt.list],[]));this.specList=specList;this.specCombinationList=specCombinationList;//根据可选规格列表矩阵创建this.initSpec();//同级顶点创建this.initSameLevel();}/***根据可选规格组合填写邻接矩阵的值*/initSpec(){this.specCombinationList.forEach((item)={this.fillInSpec(item.specs);});}//填写同级点initSameLevel(){//获得初始所有可选项constspecsOption=this.getCollection(this.vertex);this.specList.forEach((item)={constparams:AdjoinType=[];//获取同级别顶点item.list.forEach((value)={if(specsOption.includes(value))params.push(value);});//同级点位创建this.fillInSpec(params);});}/**传入顶点数组，查询出可选规格*
paramparams*/getSpecscOptions(params:AdjoinType){letspecOptionCanchoose:AdjoinType=[];if(params.some(Boolean)){//过滤一下选项specOptionCanchoose=this.getUnions(params.filter(Boolean));}else{//所有可选项specOptionCanchoose=this.getCollection(this.vertex);}turnspecOptionCanchoose;}/**params*填写邻接矩阵的值*/fillInSpec(params:AdjoinType){params.forEach((param)={this.setAdjoinVertexs(param,params);});}}页面渲染
好了到了这一步，我们已经可以在页面中使用这两个类了：
importReact,{useState,useMemo}from"act";import{useSelector}from"act-dux";import{RootState}from"../dux/ducer/root-ducer";importSpecAdjoinMatrixfrom"../utils/spec-adjoin-martix";import"./spec.css";constclassNames=qui("classnames");constSpec:React.FC=()={const{specList,specCombinationList}=useSelector((state:RootState)=state.spec);//已选择的规格，长度为规格列表的长度const[specsS,setSpecsS]=useState(Array(specList.length).fill(""));//创建一个规格矩阵constspecAdjoinMatrix=useMemo(()=newSpecAdjoinMatrix(specList,specCombinationList),[specList,specCombinationList]);//获得可选项表constoptionSpecs=specAdjoinMatrix.getSpecscOptions(specsS);consthandleClick=function(bool:boolean,text:string,index:number){//排除可选规格里面没有的规格if(specsS[index]!==text!bool)turn;//根据text判断是否已经被选中了specsS[index]=specsS[index]===text?"":text;setSpecsS(specsS.slice());};turn(divclassName="container"{specList.map(({title,list},index)=(divkey={index}pclassName="title"{title}/pdivclassName="specBox"{list.map((value,i)={constisOption=optionSpecs.includes(value);//当前规格是否可选constisActive=specsS.includes(value);//当前规格是否被选turn(spankey={i}className={classNames({specOption:isOption,specAction:isActive,specDisabled:!isOption,})}onClick={()=handleClick(isOption,value,index)}{value}/span);})}/div/div))}/div);};exportdefaultSpec;
好了，打完收工了，如果有小伙伴想看实现效果，可以查看这里，另外我已经把代码上传到Gayhub了，如果有小伙伴想把代码拉到本地看看，那么