DIV CSS 佈局教程網

JavaScript 笛卡兒積實作:用「指標」把多維選項一次配完
編輯:關於JavaScript     

笛卡兒積(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)的方式逐筆吐出,避免一次佔用大量記憶體。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved