問(wèn)題場(chǎng)景
SKU最小存貨單位(Stock Keeping Unit)在連鎖零售門店中有時(shí)稱單品為一個(gè)SKU总棵，定義為保存庫(kù)存控制的最小可用單位签杈，例如紡織品中一個(gè)SKU通常表示規(guī)格屠阻、顏色般渡、款式释牺。
逛過(guò)淘寶的人都知道一種商品可能有多種屬性類型髓削，拿一件衣服來(lái)說(shuō)，
- 性別：男葡兑、女
- 顏色：紅奖蔓、綠、藍(lán)
- 尺寸上：38讹堤、39吆鹤、40
只有3個(gè)屬性全部都選定的時(shí)候，才能真正確定你買的是哪一件衣服洲守，也才能知道衣服對(duì)應(yīng)的價(jià)格疑务、庫(kù)存等信息沾凄。
如果你只選擇了其中1或2個(gè)屬性，剩下未被選擇的屬性要進(jìn)行判斷知允，確定哪些屬性值可以被選中撒蟀，哪些不能（因?yàn)橛行﹕ku組合不存在，或者庫(kù)存為0温鸽，無(wú)法購(gòu)買）
核心問(wèn)題
- 如何根據(jù)全部屬性查詢對(duì)應(yīng)的價(jià)格保屯、庫(kù)存？
- 如何確定哪些屬性值可以被選中涤垫，哪些不能姑尺？
前者很簡(jiǎn)單，遍歷一遍所有的SKU信息列表就知道了蝠猬，或者利用Map直接獲取就行切蟋。后者比較麻煩，需要進(jìn)行多次匹配吱雏。大體思想如下：
- 遍歷SKU列表，從中選出包含
已選中屬性和屬性值的條目列表containTargetList瘾境； - 遍歷containTargetList歧杏，找出存在其中的
未被選中屬性的屬性值 - 結(jié)合
未被選中屬性的全部屬性值和未被選中屬性在containTargetList中存在的屬性值，確定未被選中屬性中哪些屬性值是不能被選中的迷守。
附錄：Python的簡(jiǎn)易實(shí)現(xiàn)版
#!/usr/bin/python
# -*- coding: utf-8 -*-
#################################
## 輸入：連續(xù)點(diǎn)擊事件
## 輸出：各個(gè)按鈕的狀態(tài)
#################################
# 不同的規(guī)格屬性
KEYS = {
"size":["38", "39", "40"],
"color":["red", "blue", "green"],
"sex":["man", "woman"],
};
# 不同的規(guī)格屬性組合對(duì)應(yīng)的 庫(kù)存和價(jià)格
SKUS = {
"39;red;man":{"price":100, "count":10},
"40;red;man":{"price":100, "count":10},
"38;grean;woman":{"price":100, "count":20},
"39;red;woman":{"price":100, "count":30},
"39;blue;man":{"price":100, "count":10},
"40;blue;man":{"price":100, "count":10},
"38;blue;woman":{"price":100, "count":20},
"39;green;woman":{"price":100, "count":30},
}
def processSku(inputData):
## 1. 預(yù)處理數(shù)據(jù)犬绒，將規(guī)格的屬性值變?yōu)閷?duì)象的屬性值，便于讀取比較
for sku in SKUS:
array = sku.split(";");
SKUS[sku]["size"] = array[0]
SKUS[sku]["color"] = array[1]
SKUS[sku]["sex"] = array[2]
## 2. 找出被選中的屬性值列表
inputDataArray = inputData.split(";");
targetedDict = {}
for data in inputDataArray:
if ":" in data:
[key, value] = data.split(":")
targetedDict[key] = value
print "已經(jīng)選中的屬性：" , targetedDict
if(len(targetedDict) == len(KEYS)):
key = "%s;%s;%s" % (targetedDict["size"],targetedDict["color"],targetedDict["sex"])
if key in SKUS:
print "所有屬性皆被選中兑凿，對(duì)應(yīng)的結(jié)果為\n" , key , ":", SKUS[key]
else:
print "所有屬性皆被選中凯力，但查無(wú)結(jié)果\n"
return;
## 3. 找出未被選中的屬性值列表
unTargetDict = {}
for key in KEYS:
if key not in targetedDict:
unTargetDict[key] = KEYS[key]
print "未被選中的屬性：" , unTargetDict
## 4. 判斷未被選中的屬性值是否能被選中
### 4.1. 遍歷規(guī)格屬性組合，找到包含`targetedDict屬性值`的所有sku組合
containTargetList = []
for skuItem in SKUS:
canAppend = True
for key in targetedDict:
if SKUS[skuItem][key] != targetedDict[key]:
canAppend = False
break;
if canAppend:
containTargetList.append(SKUS[skuItem])
print "包含選中屬性的sku條目："
for skuItem in containTargetList:
print skuItem
### 4.2 判斷每個(gè)屬性下面每個(gè)屬性值的存在狀態(tài)礼华，True表示可以選中咐鹤，F(xiàn)alse表示不能繼續(xù)選擇了
skuStaus = {}
for skuKey in unTargetDict:
skuStaus[skuKey] = {}
for skuValue in unTargetDict[skuKey]:
skuStaus[skuKey][skuValue] = False;
for skuItem in containTargetList:
for skuKey in unTargetDict:
for skuValue in unTargetDict[skuKey]:
if skuItem[skuKey] == skuValue:
skuStaus[skuKey][skuValue] = True;
break;
print "\n可繼續(xù)選中的屬性值狀態(tài)為: "
for skuKey in skuStaus:
print skuKey,":",skuStaus[skuKey]
### 測(cè)試數(shù)據(jù)
inputDatas =[
# "size:39",
"size:40;",
# "size:39;sex:woman", #選中size 39和sex:woman
# "size:39;sex:woman;color:red",
# "size:39;sex:woman;color:red1",
]
for inputData in inputDatas:
print "\n\n------Start：測(cè)試數(shù)據(jù)為%s------" % inputData
processSku(inputData)
print "------end----------------\n\n"
優(yōu)化建議：
- 如果用戶下一次選中的屬性值，沒(méi)有影響之前的屬性值選擇圣絮。也就是說(shuō)祈惶，用戶上一次選中了“男”這個(gè)屬性值，這一次選中了“40”這個(gè)屬性值扮匠，可以直接在上一次containTargetList的基礎(chǔ)上繼續(xù)過(guò)濾捧请，而不用遍歷全部的SKU列表。
Panda
2016-05-19
參考：
- Fan同學(xué)提供的算法概要
- 淘寶SKU組合查詢算法實(shí)現(xiàn)
