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

Question

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

假设我有这个：

[1, 2, 3]

我如何得到这个？

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

我对所有子集都感兴趣。具体长度的子集，参考以下问题：

查找大小为 n 的子集：1,
查找大小 > 1 的子集：1

Answer 1

我们可以从 offset 开始为输入数组的一个子集解决这个问题。然后我们递归回来得到一个完整的解决方案。

使用 generator function 允许我们迭代具有恒定内存使用的子集：

// 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ⁿ).

Answer 2

另一个简单的解决方案。

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

Answer 3

您可以轻松地从数组生成幂集，使用如下所示：

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

Answer 4

这是另一种非常优雅的解决方案，没有循环或递归，仅使用 map 和 reduce 数组本机函数。

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

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

Answer 5

let subsets = (n) => {

let result = [];
result.push([]);

n.forEach(a => {

  //array length
   let length = result.length;
    let i =0;

    while(i < length){

      let temp = result[i].slice(0);
      temp.push(a);

      result.push(temp);
      i++;

    }
})

return result;
}

Answer 6

这个是递归的

var subsets = function(s){
  if(s.length === 0) {
    return [[]]
  }
  var h,t,ss_excl_h;
  var ss_incl_h = [];
  [h,...t] = s;
  ss_excl_h = subsets(t)
  for(ss of ss_excl_h) {
    let hArr = [];
    hArr.push(h);
    let temp = hArr.concat(ss)
    ss_incl_h.push(temp);
  }
  return ss_incl_h.concat(ss_excl_h)
}

console.log(subsets([1,2,3])) // returns distinct subsets

Answer 7

我开始了解这个 post 中的示例发生了什么。虽然函数生成器示例、按位运算符示例以及数组 map 和 reduce 函数的使用示例非常优雅和令人印象深刻，但我发现很难在脑海中直观地看到到底发生了什么。我在下面有 2 个示例，我认为它们很容易将非递归和递归解决方案可视化。我希望这可以帮助其他人尝试在寻找所有子集的过程中全神贯注。

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

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]))

Answer 8

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 ] ]

Answer 9

使用flatMap和rest/spread，这可以相当优雅：

const subsets = ([x, ...xs]) =>
  x == undefined
    ? [[]]
    : subsets (xs) .flatMap (ss => [ss, [x, ...ss]]) 

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

.as-console-wrapper {max-height: 100% !important; top: 0}

此版本未按要求的顺序 return。这样做似乎不太优雅，可能有更好的版本：

const subset = (xs = []) => {
  if (xs.length == 0) {return [[]]}
  const ys = subset (xs .slice (0, -1))
  const x = xs .slice (-1) [0]
  return [... ys, ... ys .map (y => [... y, x])]
}

或者，相同的算法，不同的风格，

const subsets = (
  xs = [], 
  x = xs .slice (-1) [0], 
  ys = xs.length && subsets (xs .slice (0, -1))
) =>
  xs .length == 0
    ? [[]]
    : [... ys, ... ys .map (y => [... y, x])]

Answer 10

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

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]

Answer 11

答案的缩略版。

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]]

Answer 12

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
}

Answer 13

使用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]]

Answer 14

更新 ES2020

在 ES2020 中，BigInt 已经可用。

Bigints don’t have a fixed storage size in bits; their sizes adapt to the integers they represent.
- Dr. Axel Rauschmayer; JavaScript for impatient programmers - Chapter 18.2 BigInts

参见 source。

使用BitInts我们可以用一个binary counter来计算幂集，不再受最大整数大小的限制

使用 generator 我们还可以循环遍历具有恒定内存要求的幂集，如果你想生成一个巨大的幂集，这很重要。

这是一个使用原始数组的示例 [1, 2, 3]。

/**
 * Generate power set from a given array
 * @param {Array<any>} array array to create power set from
 */
function* powerSet(array){
  // use BigInt to be no longer limited by maximum length of 53-bits
  const size = 2n ** BigInt(array.length); 
  for (let i = 0; i < size; i++) {
    const cur = [];
    for(let j = 0; j < array.length; j++){
      // check if i-th bit is set to 1
      if((i & (1 << j)) > 0){
        // push array value (represented by that 1-bit) to result
        cur.push(array[j]);
      }
    }
    // generate next result
    yield cur;
  } 
}

// generate power set for [1, 2, 3] and print results
console.log([...powerSet([1, 2, 3])]);

.as-console-wrapper { max-height: 100% !important; top: 0; }

在这里，您如何循环遍历具有恒定内存且数组长度没有上限（理论上，在计算时间方面会有上限）的非常大的幂集。

/**
 * Generate power set from a given array
 * @param {Array<any>} array array to create power set from
 */
function* powerSet(array){
  // use BigInt to no longer limited by maximum length of 53-bits
  const size = 2n ** BigInt(array.length); 
  for (let i = 0; i < size; i++) {
    const cur = [];
    for(let j = 0; j < array.length; j++){
      // check if i-th bit is set to 1
      if((i & (1 << j)) > 0){
        // push array value (represented by that 1-bit) to result
        cur.push(array[j]);
      }
    }
    // generate next result
    yield cur;
  } 
}

/**
 * Helper function to generate an array containing more than 53 elements
 * @param {number} start 
 * @param {number} end 
 */
function* range(start, end){
  for (let i = start; i < end; i++) {
    yield i;  
  }
}

// create an array containing elments 1 through 60 ([1, 2, 3, ..., 60])
const oneToSixty = [...range(1, 61)];
let i = 0;
const max = 1000; 
// loop over whole powerSet with constant memory requirement
// abort after 1000 subsets, otherwise this will take a very long time to complete
for(const subset of powerSet(oneToSixty)){
  console.log(subset);
  if(i++ === max) break;
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

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

How to find all subsets of a set in JavaScript? (Powerset of array)

javascript

subset

powerset

更新 ES2020

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

How to find all subsets of a set in JavaScript? (Powerset of array)

javascript

subset

powerset

更新 ES2020

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