笛卡兒積(Cartesian product)在做多組條件搭配時非常常見:例如服飾的顏色、尺寸、材質各有若干選項,要列出所有可能的 SKU 組合,背後就是一道笛卡兒積。本文用純 JavaScript 手寫一版,重點放在「用指標追蹤每一維目前走到第幾個」這個核心技巧。
直覺做法是用一層又一層的巢狀迴圈,但維度是動態的時候,迴圈层数無法事先寫死。因此這裡換個角度:為每一維維護一個游標(count),全部游標都從 0 開始,每一輪依序取出各維目前指到的元素,拼成一個組合;接著只要「進位」——把最後一維往前推一格,推到底就歸零並往前一維進位,一路推到最前面也溢出為止,所有組合就列完了。
程式中另外用 parent 記錄每一維的上一層索引,就是為了讓進位時知道該回到哪一維繼續檢查。
// 笛卡兒積組合
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;
}
}
}
}
// 使用範例
var data = [
['紅', '藍'],
['S', 'M', 'L'],
['棉', '麻']
];
console.log(descartes(data).length); // 2 * 3 * 2 = 12
這個實作的重點是「用資料驅動維度」,很適合表單動態產生 SKU 這類場景。要注意組合數量會隨維度相乘而爆炸式成長,維度多、每維選項也多時,先把上層 product 組合數估算一下再決定要不要一次算完,或改用惰性產生(iteration)的方式逐筆吐出,避免一次佔用大量記憶體。