js实现组合
组合的概念
组合是从给定集合中选择若干元素，不考虑顺序的数学操作。在JavaScript中实现组合通常涉及递归或迭代方法生成所有可能的子集。
递归实现组合
递归方法通过逐步缩小问题规模生成组合，适用于元素数量较少的情况。
function combinationsRecursive(arr, k) {
if (k === 0 || k > arr.length) return [[]];
if (k === arr.length) return [arr.slice()];
const [first, ...rest] = arr;
const withoutFirst = combinationsRecursive(rest, k);
const withFirst = combinationsRecursive(rest, k - 1).map(comb => [first, ...comb]);
return [...withFirst, ...withoutFirst];
}迭代实现组合
迭代方法使用位运算或循环生成组合，适合处理较大数据集。
function combinationsIterative(arr, k) {
const result = [];
const stack = [{ index: 0, current: [] }];
while (stack.length > 0) {
const { index, current } = stack.pop();
if (current.length === k) {
result.push([...current]);
continue;
}
if (index >= arr.length) continue;
stack.push({ index: index + 1, current: [...current, arr[index]] });
stack.push({ index: index + 1, current: [...current] });
}
return result;
}库函数实现
使用现成的库函数可以简化组合生成过程，如Lodash的_.combinations。
const _ = require('lodash');
const result = _.combinations([1, 2, 3, 4], 2);性能优化建议
对于大规模数据组合计算，考虑使用生成器函数或记忆化技术减少内存消耗。
function* combinationsGenerator(arr, k) {
function* helper(start, path) {
if (path.length === k) yield path.slice();
for (let i = start; i < arr.length; i++) {
path.push(arr[i]);
yield* helper(i + 1, path);
path.pop();
}
}
yield* helper(0, []);
}应用场景示例
组合算法常用于：
- 彩票号码生成
- 商品搭配推荐
- 密码破解中的字符组合尝试
- 机器学习中的特征选择
注意事项
递归方法在组合元素较多时可能导致栈溢出，迭代方法通常更安全。实际应用中应根据数据规模选择合适方法，必要时进行分批次处理。
