應用場景
- SKU 規格組合生成(顏色 × 尺寸 × 套餐)
- 測試用例全排列
- 多條件篩選器組合
通用實現(支援對象鍵名與數組)
function descartes(list) {
// list: {color: ['紅','藍'], size: ['S','M']} 或 [['紅','藍'], ['S','M']]
var isObj = Object.prototype.toString.call(list) === '[object Object]';
var keys = isObj ? Object.keys(list) : null;
var arrs = isObj ? keys.map(k => list[k]) : list;
// 指針對象:每維當前索引
var pointers = arrs.map(() => 0);
var result = [];
while (true) {
// 組合當前指針對應的值
var combo = isObj ? {} : [];
for (var i = 0; i < arrs.length; i++) {
var val = arrs[i][pointers[i]];
isObj ? (combo[keys[i]] = val) : combo.push(val);
}
result.push(combo);
// 進位邏輯:從最後一維向前檢查是否越界
var dim = arrs.length - 1;
while (dim >= 0) {
pointers[dim]++;
if (pointers[dim] < arrs[dim].length) break; // 該維未越界,停止進位
pointers[dim] = 0; // 歸零
dim--; // 向高維進位
}
if (dim < 0) break; // 最高維也越界 → 全部組合完成
}
return result;
}
// 測試
console.log(descartes({ color: ['紅','藍'], size: ['S','M'] }));
// [{color:'紅',size:'S'},{color:'紅',size:'M'},{color:'藍',size:'S'},{color:'藍',size:'M'}]
console.log(descartes([['A','B'], [1,2,3]]));
// [['A',1],['A',2],['A',3],['B',1],['B',2],['B',3]]
遞歸版本(更易理解)
function descartesRecursive(list) {
var keys = Object.keys(list);
function dfs(idx, current) {
if (idx === keys.length) { result.push({...current}); return; }
var key = keys[idx];
for (var v of list[key]) {
current[key] = v;
dfs(idx + 1, current);
}
}
var result = [];
dfs(0, {});
return result;
}
性能與優化
- 時間複雜度 O(N₁×N₂×...×Nₖ),組合數爆炸時慎用(如 >10 萬條)
- 大數據量改用 **生成器** 按需產出:
function* descartesGen(list) {
var keys = Object.keys(list);
var arrs = keys.map(k => list[k]);
var pointers = arrs.map(() => 0);
while (true) {
yield keys.reduce((o, k, i) => (o[k] = arrs[i][pointers[i]], o), {});
var dim = arrs.length - 1;
while (dim >= 0) {
pointers[dim]++;
if (pointers[dim] < arrs[dim].length) break;
pointers[dim] = 0; dim--;
}
if (dim < 0) return;
}
}
// 使用
for (var combo of descartesGen({a:[1,2], b:[3,4]})) { console.log(combo); }