DIV CSS 佈局教程網

JavaScript 實現笛卡爾積組合算法
編輯:JavaScript綜合知識     

笛卡爾積在多維選項組合、商品規格 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 種組合

需要提醒的是,笛卡爾積的結果數量隨維度相乘增長,維度稍多就會爆炸。實際業務中若只需要部分組合,建議加上條件過濾,避免生成後再大量丟棄。

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