萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 笛卡爾積算法實現:多維數組/對象組合生成器

應用場景

  • 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); }
copyright © 萬盛學電腦網 all rights reserved