JavaScript 笛卡尔积算法实现：从数组生成所有组合

笛卡尔积的核心逻辑

笛卡尔积是指多个集合的所有可能有序配对。在编程中，若给定 [['A', 'B'], [1, 2]]，其笛卡尔积为 [['A', 1], ['A', 2], ['B', 1], ['B', 2]]。核心思路是将每个子数组视为一个“位”，通过模拟数字进位机制来遍历所有状态。

算法实现步骤

第1步：初始化指针与数据结构

首先需要解析输入的多维数组，为每个维度创建一个指针对象，记录当前索引位置（count）和上一级父节点索引（parent），以便进行回溯。

function descartes(list) {
  var point = {}; // 存储每个维度的指针状态
  var result = []; // 最终结果集
  var pIndex = null; // 记录最后一个非空维度的索引
  var temp = []; // 临时存储当前组合
  var tempCount = 0;

  // 构建指针映射表
  for (var index in list) {
    if (typeof list[index] == 'object') {
      // parent 用于记录前一个有效维度的索引，实现回溯
      point[index] = { 'parent': pIndex, 'count': 0 };
      pIndex = index;
    }
  }

第2步：处理单维度数据边界情况

如果输入数组只包含一层数据（即没有嵌套子数组或只有一个子数组），直接返回原数组。这是算法的必要终止条件之一，避免无效计算。

  // 若不存在有效的嵌套结构，直接返回输入数据
  if (pIndex == null) {
    return list;
  }

第3步：动态循环生成组合

使用外层 while(true) 循环持续生成组合，直到所有状态遍历完毕。内层循环负责读取当前指针指向的元素，拼凑成一组完整组合并存入 result。

  while (true) {
    // 重置临时数组，准备收集新一行数据
    temp = [];
    
    // 遍历所有维度，取当前指针位置的元素
    for (var index in list) {
      tempCount = point[index]['count'];
      temp.push(list[index][tempCount]);
    }
    
    // 将当前组合压入结果数组
    result.push(temp);  

第4步：执行进位与回溯检查

这是算法最关键的逻辑。生成一组后，需尝试将最后一个维度的指针加 1。如果当前维度已到达最大长度（发生溢出），则将指针重置为 0，并向上一级（父节点）进位。若最高级也发生溢出且无父节点，说明全部遍历完成，返回结果。

    // 检查是否需要进位/回溯
    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 {
        // 未溢出：当前位计数+1，跳出内层循环开始下一轮组合
        point[index]['count']++;
        break;
      }
    }
  }
}

使用示例与验证

以下是一个简单的测试用例，展示如何调用该函数：

var data = [
  ['红色', '蓝色'],
  ['S', 'M', 'L'],
  ['棉', '涤纶']
];
console.log(descartes(data));

输出将包含 $2 \times 3 \times 2 = 12$ 种不同的商品属性组合。该算法时间复杂度为 $O(N)$，其中 N 为最终生成的组合总数，空间复杂度亦与此相关，适合处理常规规模的配置组合需求。

注意事项

• 数据类型检查：算法假设输入数组中的子元素均为可枚举的对象或数组。若包含非数组的子项，可能需要增加类型判断以增强健壮性。
• 性能考量：笛卡尔积的结果集随维度数量呈指数级增长，当维度较多时（如超过5-6维），可能导致内存占用激增，建议在实际项目中结合分页或虚拟化技术使用。

以上就是 JavaScript 笛卡尔积算法实现的详细内容，更多关于 JavaScript 算法优化的资料请关注本站其它相关文章！