两年前看过一篇淘宝UED开源的sku算法(js实现)，当时并没有静下心来仔细研究一下，只觉得乍一看好难。这两天无意中github搜了一下，想找找java实现版，还真被我找到了。于是静下心来好好讨教了一番算法的高深。
在一番推敲之后终于看透其真谛，遂决心组织一下语言，记录我所理解的内容。
核心类SKU.java
public class Sku {
/**
* 算法入口
*
* @param initData 所有库存的hashMap组合
* @return 拆分所有组合产生的所有情况（生成客户端自己的字典）
*/
public static Map<String, BaseSkuModel> skuCollection(Map<String, BaseSkuModel> initData) {
//用户返回数据
HashMap<String, BaseSkuModel> result = new HashMap<>();
// 遍历所有库存
for (String subKey : initData.keySet()) {
BaseSkuModel skuModel = initData.get(subKey);
//根据；拆分key的组合
String[] skuKeyAttrs = subKey.split(";");
//获取所有的组合
ArrayList<ArrayList<String>> combArr = combInArray(skuKeyAttrs);
// 对应所有组合添加到结果集里面
for (int i = 0; i < combArr.size(); i++) {
add2SKUResult(result, combArr.get(i), skuModel);
}
// 将原始的库存组合也添加进入结果集里面
String key = TextUtils.join(";", skuKeyAttrs);
result.put(key, skuModel);
}
return result;
}
/**
* 获取所有的组合放到ArrayList里面
*
* @param skuKeyAttrs 单个key被； 拆分的数组
* @return ArrayList
*/
private static ArrayList<ArrayList<String>> combInArray(String[] skuKeyAttrs) {
if (skuKeyAttrs == null || skuKeyAttrs.length <= 0)
return null;
int len = skuKeyAttrs.length;
ArrayList<ArrayList<String>> aResult = new ArrayList<>();
for (int n = 1; n < len; n++) {
ArrayList<Integer[]> aaFlags = getCombFlags(len, n);
for (int i = 0; i < aaFlags.size(); i++) {
Integer[] aFlag = aaFlags.get(i);
ArrayList<String> aComb = new ArrayList<>();
for (int j = 0; j < aFlag.length; j++) {
if (aFlag[j] == 1) {
aComb.add(skuKeyAttrs[j]);
}
}
aResult.add(aComb);
}
}
return aResult;
}
private static ArrayList<Integer[]> getCombFlags(int len, int n) {
if (n <= 0) {
return new ArrayList<>();
}
ArrayList<Integer[]> aResult = new ArrayList<>();
Integer[] aFlag = new Integer[len];
boolean bNext = true;
int iCnt1 = 0;
//初始化
for (int i = 0; i < len; i++) {
aFlag[i] = i < n ? 1 : 0;
}
aResult.add(aFlag.clone());
while (bNext) {
iCnt1 = 0;
for (int i = 0; i < len - 1; i++) {
if (aFlag[i] == 1 && aFlag[i + 1] == 0) {
for (int j = 0; j < i; j++) {
aFlag[j] = j < iCnt1 ? 1 : 0;
}
aFlag[i] = 0;
aFlag[i + 1] = 1;
Integer[] aTmp = aFlag.clone();
aResult.add(aTmp);
if (!TextUtils.join("", aTmp).substring(len - n).contains("0")) {
bNext = false;
}
break;
}
if (aFlag[i] == 1) {
iCnt1++;
}
}
}
return aResult;
}
/**
* 添加到数据集合
*
* @param result
* @param newKeyList
* @param skuModel
*/
private static void add2SKUResult(HashMap<String, BaseSkuModel> result, ArrayList<String> newKeyList, BaseSkuModel skuModel) {
String key = TextUtils.join(";", newKeyList);
if (result.keySet().contains(key)) {
result.get(key).setStock(result.get(key).getStock() + skuModel.getStock());
result.get(key).setPrice(skuModel.getPrice());
} else {
result.put(key, new BaseSkuModel(skuModel.getPrice(), skuModel.getStock()));
}
}
}
首先说下大体思路
- 通过后台获取类似
{
"1;4":{"price":10,"count":10}
"1;5":{"price":10,"count":20}
"1;7":{"price":10,"count":30}
}
这样的数据结构。客户端根据数据自行生成字典放在HashMap里面
- 我们要做的就是把上面的map中的key做拆分再组成新的map,以此来得到所有属性组合,以及对应sku对象(自定义一个包含price和count的对象)
补充:
假设后台给到属性组合[3,4,2],通过算法我们要得到[[3],[4],[2],[3,4],[3,2],[4,2]],然后把该二阶数组里的每个数组当做key来组成新的map。即add2SKUResult()方法做的事情。
核心方法combInArray(String[] skuKeyAttrs)
该方法做的事情概括下来就是获得在m个数中取n个的所有组合。
听起来很简单?
实则不然。(敲黑板)
下面我们用具体的某个数组来解释整个算法，看起来会更清晰一点。
以属性集合[3,4,2]为例
入参skuKeyAttrs=[3,4,2]
for (int n = 1; n < len; n++) {
ArrayList<Integer[]> aaFlags = getCombFlags(len, n);
for (int i = 0; i < aaFlags.size(); i++) {
Integer[] aFlag = aaFlags.get(i);
ArrayList<String> aComb = new ArrayList<>();
for (int j = 0; j < aFlag.length; j++) {
if (aFlag[j] == 1) {
aComb.add(skuKeyAttrs[j]);
}
}
aResult.add(aComb);
}
}
- 从下标1开始循环到数组末位，
getCombFlags()用来"标记"skuKeyAttrs中 "n个数的组合结果"。 这句话有点难懂(博主也觉得很难用语言描述 - -),下面详述。 - 循环
getCombFlags()的结果集--二阶数组aaFlags,循环其中每个数组aFlag,当aFlag中有值=1时，取skuKeyAttrs[当前下标]存入结果集
if (aFlag[j] == 1) {
aComb.add(skuKeyAttrs[j]);
}
那么我们先来理解getCombFlags()这个方法，理解了这个方法，那么毫不夸张的说整个类也就理解了90%了。
getCombFlags
这里就直接以注释来解释了
ArrayList<Integer[]> aResult = new ArrayList<>();
Integer[] aFlag = new Integer[len];
boolean bNext = true;
/*
* 连续的"1"个数计数器
* 它的值=连续"1"的个数-1
*
* */
int iCnt1 = 0;
//初始化
/*
* n=1:
* aFlag=[1,0,0]
* n=2:
* aFlag=[1,1,0]
*
* */
for (int i = 0; i < len; i++) {
aFlag[i] = i < n ? 1 : 0;
}
aResult.add(aFlag.clone());
while (bNext) {
iCnt1 = 0;
/*
* 当满足i位=1,i+1位=0时需要把i位的1往后移一位并且把i位的值置为0
* 来获得新的组合方式
*
* */
for (int i = 0; i < len - 1; i++) {
if (aFlag[i] == 1 && aFlag[i + 1] == 0) {
/*
* 分离连续"1"
* */
for (int j = 0; j < i; j++) {
aFlag[j] = j < iCnt1 ? 1 : 0;
}
//初始化时已经把第一种情况加入aResult
/*
* 这里相当于把第i位和第i+1位互换
* (因为数组值里只有0和1)
*
* 以aFlag=[1,0,0]初始值为例
* i=0:
* aFlag=[0,1,0]
* */
aFlag[i] = 0;
aFlag[i + 1] = 1;
Integer[] aTmp = aFlag.clone();
aResult.add(aTmp);
/*
* 去掉前len-n个字符,留下的字符中如果不包含0
* 那么说明我们把1都变换到末位了,即取完了n个数的所有组合。
*
* */
if (!TextUtils.join("", aTmp).substring(len - n).contains("0")) {
bNext = false;
}
break;
}
if (aFlag[i] == 1) {
iCnt1++;
}
}
}
可能看完注释你还是有点懵。我们再来整理一遍。
当len=3,n=1,我们返回的数组是这样的[[1,0,0],[0,1,0],[0,0,1]]。那么在combInArray中会取到[[3],[4],[2]]
当len=3,n=2,我们返回的数组是这样的[[1,1,0],[1,0,1],[0,1,1]]。那么在combInArray中会取到[[3,4],[3,2],[4,2]]
不难发现getCombFlags()告诉了combInArray用哪些下标来组成最终的集合。
至此,终于理解了getCombFlags()中每一句的目的。相信其他方法都不难理解。本篇也不再过多解释了。
我很想搞明白这样的思路是如何产生的，不得不感叹算法的巧妙，也希望看到本篇的同学不吝赐教。
致谢
感谢 N.Sun同学翻译成java
github项目地址
感谢各位同学耐心看完!
