js实现组合

实现组合的 JavaScript 方法

在 JavaScript 中，组合通常指从一组元素中选取若干元素的所有可能方式（不考虑顺序）。以下是几种常见的实现方法：

递归法

递归是解决组合问题的经典方法，通过不断缩小问题规模来生成所有组合。

function combinations(arr, k) {
  if (k === 0 || k > arr.length) return [];
  if (k === arr.length) return [arr];
  if (k === 1) return arr.map(item => [item]);

  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = arr.slice(i + 1);
    const subCombinations = combinations(rest, k - 1);
    subCombinations.forEach(combo => {
      result.push([arr[i], ...combo]);
    });
  }
  return result;
}

迭代法

使用位运算或循环来生成组合，适合处理较大数据集。

function combinations(arr, k) {
  const result = [];
  const n = arr.length;
  const total = 1 << n;

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

生成器法

使用 ES6 生成器函数实现按需生成组合，节省内存。

function* combinations(arr, k) {
  if (k === 1) {
    for (const item of arr) yield [item];
    return;
  }

  for (let i = 0; i <= arr.length - k; i++) {
    for (const combo of combinations(arr.slice(i + 1), k - 1)) {
      yield [arr[i], ...combo];
    }
  }
}

使用示例

const arr = [1, 2, 3, 4];
console.log(combinations(arr, 2));
// 输出: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

性能优化建议

对于大数据集，递归方法可能导致栈溢出。可以考虑使用迭代法或限制递归深度。Lodash 等库也提供了组合生成工具函数，适合生产环境使用。