js实现组合

组合问题的基本概念

组合是指从一组元素中选出若干个元素，不考虑顺序。例如从数组 [1, 2, 3] 中选出 2 个元素，可能的组合为 [1,2], [1,3], [2,3]。

递归实现组合

递归是解决组合问题的经典方法，通过逐步缩小问题规模并合并结果：

function combinations(arr, k) {
  if (k === 0) return [[]];
  if (arr.length === 0) return [];

  const first = arr[0];
  const rest = arr.slice(1);

  const withFirst = combinations(rest, k - 1).map(comb => [first, ...comb]);
  const withoutFirst = combinations(rest, k);

  return [...withFirst, ...withoutFirst];
}

// 示例用法
console.log(combinations([1, 2, 3], 2)); 
// 输出: [[1, 2], [1, 3], [2, 3]]

迭代实现组合

使用位运算可以迭代生成所有可能的组合：

function combinationsIterative(arr, k) {
  const result = [];
  const n = arr.length;

  for (let mask = 0; mask < (1 << n); mask++) {
    if (countSetBits(mask) !== k) continue;

    const current = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) current.push(arr[i]);
    }
    result.push(current);
  }

  return result;
}

function countSetBits(num) {
  let count = 0;
  while (num) {
    count += num & 1;
    num >>= 1;
  }
  return count;
}

// 示例用法
console.log(combinationsIterative([1, 2, 3], 2));
// 输出: [[1, 2], [1, 3], [2, 3]]

使用生成器实现组合

ES6 生成器可以惰性地生成组合，节省内存：

function* combinationsGenerator(arr, k, start = 0, current = []) {
  if (current.length === k) {
    yield [...current];
    return;
  }

  for (let i = start; i < arr.length; i++) {
    current.push(arr[i]);
    yield* combinationsGenerator(arr, k, i + 1, current);
    current.pop();
  }
}

// 示例用法
const gen = combinationsGenerator([1, 2, 3], 2);
console.log([...gen]); 
// 输出: [[1, 2], [1, 3], [2, 3]]

处理大型数据集的优化

对于大型数据集，可以采用剪枝策略优化递归：

function optimizedCombinations(arr, k) {
  const result = [];

  function backtrack(start, path) {
    if (path.length === k) {
      result.push([...path]);
      return;
    }

    const maxRemaining = arr.length - (k - path.length) + 1;
    for (let i = start; i < maxRemaining; i++) {
      path.push(arr[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

实际应用示例

从颜色列表中生成所有可能的双色组合：

const colors = ['red', 'green', 'blue', 'yellow'];
const colorPairs = combinations(colors, 2);

console.log(colorPairs);
// 输出: [['red', 'green'], ['red', 'blue'], ..., ['blue', 'yellow']]

这些方法覆盖了从基础到进阶的组合生成需求，可以根据具体场景选择最适合的实现方式。递归方法直观但可能堆栈溢出，迭代方法适合确定性问题，生成器适合流式处理大数据集。