如何在 JavaScript 中查找集合的所有子集？（数组的幂集）
IT技术
javascript
subset
powerset
2021-01-17 10:40:18
6个回答
这是另一种非常优雅的解决方案，没有循环或递归，仅使用 map 和 reduce 数组本机函数。
const getAllSubsets =
theArray => theArray.reduce(
(subsets, value) => subsets.concat(
subsets.map(set => [value,...set])
),
[[]]
);
console.log(getAllSubsets([1,2,3]));我们可以为输入数组的一个子集解决这个问题，从 开始offset。然后我们递归回来得到一个完整的解决方案。
使用生成器函数允许我们迭代具有恒定内存使用量的子集：
// Generate all array subsets:
function* subsets(array, offset = 0) {
while (offset < array.length) {
let first = array[offset++];
for (let subset of subsets(array, offset)) {
subset.push(first);
yield subset;
}
}
yield [];
}
// Example:
for (let subset of subsets([1, 2, 3])) {
console.log(subset);
}运行时复杂度与解决方案的数量 (2ⁿ) 乘以每个解决方案的平均长度 (n/2) = O(n2ⁿ) 成正比。
另一个简单的解决方案。
function getCombinations(array) {
function fork(i, t) {
if (i === array.length) {
result.push(t);
return;
}
fork(i + 1, t.concat([array[i]]));
fork(i + 1, t);
}
var result = [];
fork(0, []);
return result;
}
var data = [1, 2, 3],
result = getCombinations(data);
console.log(result);.as-console-wrapper { max-height: 100% !important; top: 0; }您可以使用如下所示的方法轻松地从数组生成 powerset：
var arr = [1, 2, 3];
function generatePowerSet(array) {
var result = [];
result.push([]);
for (var i = 1; i < (1 << array.length); i++) {
var subset = [];
for (var j = 0; j < array.length; j++)
if (i & (1 << j))
subset.push(array[j]);
result.push(subset);
}
return result;
}
console.log(generatePowerSet(arr));在函数的整个主循环中，子集被创建，然后被推送到result数组中。
没有递归的简单解决方案：
function getAllSubsets(array) {
const subsets = [[]];
for (const el of array) {
const last = subsets.length-1;
for (let i = 0; i <= last; i++) {
subsets.push( [...subsets[i], el] );
}
}
return subsets;
}
它是如何工作的？
如果我们有一些从输入数字生成的子集，并且我们想在我们的输入数组中再添加一个数字，这意味着我们可以获取所有已经存在的子集，并通过将新数字附加到每个现有子集来生成新的子集。
这是一个例子 [1, 2, 3]
从一个空子集开始：
[]通过向每个现有子集添加“1”来创建新子集。这将是：
[][1]通过向每个现有子集添加“2”来创建新子集。这将是：
[], [1][2], [1, 2]通过向每个现有子集添加“3”来创建新子集。这将是：
[], [1], [2], [1, 2][3], [1, 3], [2, 3], [1, 2, 3]
其它你可能感兴趣的问题