如何用JavaScript生成数组的三元组合（非排列）？

问题描述 #

现有一个包含16个元素的数组，每个元素是长度为2的子数组，示例结构如下：

[['one', 'blue'], ['one', 'red'], ['two', 'blue'], ['two', 'red'], ...]

需要生成所有3个元素的组合（非排列，即不考虑顺序，排除不同顺序的重复组合），输出示例如下：

[[['one', 'blue'], ['one', 'red'], ['two', 'blue']],
 [['one', 'blue'], ['one', 'red'], ['two', 'red']],
 [['one', 'blue'], ['two', 'blue'], ['two', 'red']],
 [['one', 'red'], ['two', 'blue'], ['two', 'red']], ...]

已通过Python的itertools.combinations实现该功能，寻求JavaScript的等价实现方案。

实现思路 #

组合的核心是只选取原数组中索引严格递增的元素，这样就能天然避免顺序不同的重复组合（比如不会同时出现[a,b,c]和[b,a,c]，因为后者的索引顺序不满足递增要求）。

代码实现 #

1. 递归实现（简洁直观） #

这是通用的组合生成函数，支持生成任意数组中k个元素的组合：

function combinations(arr, k) {
  const result = [];
  
  const backtrack = (start, current) => {
    // 当当前组合长度达到k时，存入结果
    if (current.length === k) {
      result.push([...current]);
      return;
    }
    // 从start索引开始遍历，保证后续元素索引递增
    for (let i = start; i < arr.length; i++) {
      current.push(arr[i]);
      backtrack(i + 1, current);
      current.pop(); // 回溯，移除当前元素以尝试下一个可能
    }
  };
  
  backtrack(0, []);
  return result;
}

2. 测试示例 #

用示例输入数组验证：

// 示例输入（实际为16个元素）
const inputArray = [
  ['one', 'blue'],
  ['one', 'red'],
  ['two', 'blue'],
  ['two', 'red']
];

// 生成3元素组合
const threeElementCombinations = combinations(inputArray, 3);

// 输出结果
console.log(threeElementCombinations);

输出结果与需求示例完全一致，无重复排列组合。

3. 迭代实现（无递归） #

如果偏好非递归写法，可使用索引迭代的方式：

function combinationsIterative(arr, k) {
  const result = [];
  const totalElements = arr.length;
  // 初始化索引数组，比如k=3时初始为[0,1,2]
  let indices = Array.from({ length: k }, (_, idx) => idx);

  while (true) {
    // 根据当前索引生成组合并存入结果
    result.push(indices.map(i => arr[i]));

    // 寻找下一组合法索引
    let currentIdx = k - 1;
    // 从后往前找第一个可以递增的索引
    while (currentIdx >= 0 && indices[currentIdx] === totalElements - k + currentIdx) {
      currentIdx--;
    }
    // 所有组合生成完毕，退出循环
    if (currentIdx < 0) break;

    indices[currentIdx]++;
    // 更新后续索引为当前索引+1、+2...保证递增
    for (let j = currentIdx + 1; j < k; j++) {
      indices[j] = indices[j - 1] + 1;
    }
  }

  return result;
}

说明 #

两种实现的逻辑均与Python的itertools.combinations完全对齐，生成的组合顺序、内容一致，且不会产生重复的排列结果。

内容的提问来源于stack exchange，提问作者Brian