如何在JavaScript中找到一个集合的所有子集？（数组的幂集）

Question

我需要获取一个数组的所有可能子集。

比如说，我有这个数组：

[1, 2, 3]

我该如何获得这个？

[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]

我对所有子集都感兴趣。对于特定长度的子集，请参考以下问题：

• 查找大小为n的子集：1，2
• 查找大小大于1的子集：1

- le_m

---

[1, 1]或者[1, 2, 1]的输出会是什么？ - ibrahim mahrir

如果我们将输入的数组视为一个集合，则假定每个元素具有不同的标识。因此，[1, 1] 的幂集可能是 [], [1], [1], [1, 1] - 但如果您有更好的想法，请发表。@ibrahimmahrir - le_m

Answer 1

这里还有一个非常优雅的解决方案，没有循环或递归，只使用了map和reduce数组本地函数。

const getAllSubsets = 
      theArray => theArray.reduce(
        (subsets, value) => subsets.concat(
         subsets.map(set => [value,...set])
        ),
        [[]]
      );

console.log(getAllSubsets([1,2,3]));

- MennyMez

---

如果将[value,...set]反转为[...set,value]，它也会保留顺序。 - user3071643

这种方法不够内存高效。 - John Anisere

这种方法经常会卡住。不友好内存。 - Cozzbie

适用于较小的数组。 - ICW

一个很好的反面例子。非常简短并不意味着非常优雅。这种方法的问题正如它听起来的那样——没有循环、没有递归等等，一切都由引擎在后台完成，所以你只能看到魔法，而不理解背后发生了什么。如果所有东西都写得清晰明了、易读易懂就太好了。简洁可能是才华的姐妹，但却不是理解的朋友。 - Yuri Predborski

这种方法仅使用本地JavaScript方法。如果你认为这是魔法，那么你应该学习JavaScript的基础知识，比如reduce()和map()，而不是因为自己的误解而责怪一种非常合理且易懂的解决方案。 - dmuensterer

Answer 2

我们可以解决输入数组的一个子集问题，从 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ⁿ)。

- le_m

---

很好地使用了生成器函数！您能指出一篇更详细介绍使用“常量内存使用”的生成器函数的文章吗？ - Shaheen Ghiassy

生成器是可以退出并稍后重新进入的函数。它们的上下文（变量绑定）将在重新进入时保存。递归深度由数组长度限制，每次递归都会将一个元素推送到当前子集，直到完成为止 - 因此for (let subset of subsets(array))的每次迭代的内存使用量受到array长度的限制，假设为n而不是2^n，如果我们首先构建所有子集，然后再迭代它们，那么情况就会是这样。 - le_m

根据我的理解，使用生成器的这种实现方式似乎在O(n)内存增长方面有所增加。根据我的性能测试，在生成器的第一次迭代（即.next()），我们正在从0...n实例化所有生成器函数。与尾递归以O(1)的内存增长率增长不同，这似乎以O(n)的速度增长...顺便说一句 - 我希望我的分析是错误的，因为生成器方法似乎是一种优雅的方法。（附注：我发现了一篇优质文章：https://medium.com/javascript-scene/7-surprising-things-i-learned-writing-a-fibonacci-generator-4886a5c87710） - Shaheen Ghiassy

@ShaheenGhiassy 我不理解“以O(1)的内存增长率增长” - 内存复杂度不能是O(1)，因为每个子集已经占用了O(n)的空间。你说的“以O(n)的内存增长率增加”是什么意思 - 总空间复杂度是O(n)，其中n是数组长度？ - le_m

是的，我明白你的观点@le_m。我只是想知道是否有可能递归使用生成器并仍然实现恒定的内存使用？也许对于这个特定的问题不可能，但我知道ES6引入了尾调用优化。通过该优化，像生成斐波那契数列这样的问题可以实现恒定的内存使用，而不管递归次数（我称之为“O（1）内存增长”）。似乎生成器不会像尾调用函数一样进行优化。请参见：http://benignbemine.github.io/2015/07/19/es6-tail-calls - Shaheen Ghiassy

Answer 3

无需递归的简单解决方案：

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]

- koorchik

---

非常好的解决方案，感谢您！顺便说一下，如果您想要没有第一个元素的组合，只需返回 subsets.slice(1)。 - icosmin

Answer 4

另一个简单的解决方案。

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; }

- Nina Scholz

---

只是好奇：.as-console-wrapper 的目的是什么？ - le_m

它会产生更多的控制台输出。 - Nina Scholz

学习这段代码有助于我理解这个解决方案的策略和工作原理。太棒了！ - Matt West

Answer 5

您可以轻松地从数组生成幂集，类似以下方式：

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数组。

- Angelos Chalaris

---

一种可靠的非递归解决方案。将result.push(subset)移出循环增量，放到循环体中可能会提高可读性。如果您已经转向使用位运算：Math.pow(2, j) == 1 << j - le_m

我正在努力理解这个答案的直觉。我理解二进制字符串中的1表示元素是否包含在子集中的概念。例如，['a'，'b'，'c']，101 => ['a'，'c']。我也知道幂集有2^n个元素。但我还没有直观地理解它们如何优雅地联系在一起。顺便说一下，在jsperf上，1 << j比Math.pow(2，j)快10倍。 - Zack Burt

我喜欢这里聪明地运用数学和二进制。一个真正的计算机科学家。 - Emmanuel Aliji

有人能解释一下这段代码中的位运算对什么产生影响吗？非常感谢！ - haptn

Answer 6

我着手理解本文中的示例是如何运作的。虽然函数生成器示例、位运算符示例和将数组映射和缩减函数示例的使用非常优雅而令人印象深刻，但我觉得很难在脑海中精确地想象出具体发生了什么。下面有两个示例，我认为它们都易于可视化，一个是非递归解决方案，另一个是递归解决方案。我希望这可以帮助其他人理解找到所有子集的过程。

非递归解决方案：对于数组的每个值，克隆所有现有的子集（包括空集），并将新值添加到每个克隆体中，将克隆体推回到结果中。

const PowerSet = array => {
  const result = [[]] // Starting with empty set
  
  for (let value of array) { // For each value of the array
     const length = result.length // Can't use result.length in loop since 
                                  // results length is increased in loop
      for (let i = 0; i < length; i++){
        let temp = result[i].slice(0) // Make a clone of the value at index i  
        temp.push(value) // Add current value to clone
        result.push(temp) // Add clone back to results array
      }
  }
  
  return result;
  }

  console.log(PowerSet([1,2,3]))

递归方法： 通过递归地将当前索引值与逐渐增长的前缀值数组连接起来的组合推入幂集中。

const powerSetRecursive = (arr, prefix=[], set=[[]]) => {
  if(arr.length === 0) return// Base case, end recursion
  
  for (let i = 0; i < arr.length; i++) {
      set.push(prefix.concat(arr[i]))// If a prefix comes through, concatenate value
      powerSetRecursive(arr.slice(i + 1), prefix.concat(arr[i]), set)
      // Call function recursively removing values at or before i and adding  
      // value at i to prefix
  }
  return set
}

console.log(powerSetRecursive([1,2,3]))

- CodeBloodedChris

Answer 7

function subSets(num){


/*
example given number : [1,3]
         []
 1:  copy   push 1
    []        [1]
  
 3: copy      push 3
    [] [1] [3] [1,3]


*/
  let result = [];

  result.push([]);

  for(let i=0; i < num.length;i++){

    let currentNum = num[i];
    let len = result.length;

    for(let j=0; j < len; j++){
      let cloneData = result[j].slice();
      cloneData.push(currentNum);
      result.push(cloneData)
    }
  }

  return result;
}

let test = [1,3];
console.log(subSets(test))//[ [], [ 1 ], [ 3 ], [ 1, 3 ] ]

- ASHISH R

Answer 8

使用 reduceRight 方法：

const subsets = array =>
  array.reduceRight(
    (accumulator, a) => [...accumulator, ...accumulator.map(b => [a, ...b])],
    [[]]
  );
console.log(subsets([1, 2, 3]));  // [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

- Sash Sinha

Answer 9

@koorchik的回答的简化版本。

var getAllSubsets = (nums) => {
  const subsets = [[]];
  for (n of nums) {
    subsets.map((el) => {
      subsets.push([...el, n]);
    });
  }
  return subsets;
};

console.log(getAllSubsets([1, 2, 3])); 
// [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

- Penny Liu

Answer 10

For循环：

function powerSet(numbers) {
    const subsets = [[]]
    for (const number of numbers) {
        subsets.forEach(subset => subsets.push([...subset, number]))
    }
    return subsets
}

递归：

function powerSet(numbers) {
    const subsets = [[]]
    if (numbers.length === 0) return subsets
    for (let i = 0; i < numbers.length; i++) {
        subsets.push(...powerSet(numbers.slice(i + 1)).map(subset => [numbers[i], ...subset]))
        // Or step by step:
        // const number = numbers[i]
        // const otherNumbers = numbers.slice(i + 1)
        // const otherNumbersSubsets = powerSet(otherNumbers)
        // const otherNumbersSubsetsWithNumber = otherNumbersSubsets.map(subset => [number, ...subset])
        // subsets.push(...otherNumbersSubsetsWithNumber)
    }
    return subsets
}

- Martin Jaskulla