笛卡爾積在多維選項組合、商品規格 SKU 枚舉、參數配對這類需求裡非常常見:給出若干組取值,把它們所有可能的交叉組合全部列出來。本文給出一個能同時處理對象與數組的實現。
把每一維視為一個「指針」,指針指向該維當前的取值下標。每輪遍歷各維指針組出一個結果;然後從最後一維開始檢查是否需要進位——如果某維指針已越界就歸零並讓前一維加一,全部維度都越界時說明枚舉完畢,退出循環。
本質上這是一個以各維長度為「基數」的混合進制計數器。
// 笛卡爾積組合
function descartes(list) {
// parent 記錄上一級索引,count 是指針計數
var point = {};
var result = [];
var pIndex = null;
var tempCount = 0;
var temp = [];
// 為每個數組類型的維度建立指針對象
for (var index in list) {
if (typeof list[index] == 'object') {
point[index] = { 'parent': pIndex, 'count': 0 };
pIndex = index;
}
}
// 只有一維(或沒有可展開的維度)時直接返回
if (pIndex == null) {
return list;
}
while (true) {
// 按當前指針組出一組結果
for (var index in list) {
tempCount = point[index]['count'];
temp.push(list[index][tempCount]);
}
result.push(temp);
temp = [];
// 指針進位檢查
while (true) {
if (point[index]['count'] + 1 >= list[index].length) {
// 當前維越界,歸零並回到上一維
point[index]['count'] = 0;
pIndex = point[index]['parent'];
if (pIndex == null) {
return result; // 全部維度都走完
}
index = pIndex;
} else {
point[index]['count']++;
break;
}
}
}
}
descartes([
['白', '黑'],
['S', 'M', 'L'],
['長袖', '短袖']
]);
// => 共 2 × 3 × 2 = 12 種組合
需要提醒的是,笛卡爾積的結果數量隨維度相乘增長,維度稍多就會爆炸。實際業務中若只需要部分組合,建議加上條件過濾,避免生成後再大量丟棄。