如何在JavaScript中查找集合的所有子集？

Question

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

说我有这个:

[1, 2, 3]

我怎么得到这个？

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

我对所有子集感兴趣.有关特定长度的子集,请参阅以下问题:

• 大小为n的子集找到:1,2
• 查找大小> 1:1的子集

Answer 1

这是一个非常优雅的解决方案,没有循环或递归,只使用map和reduce数组本机函数.

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

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

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

运行时复杂度与每个解的平均长度(n/2)= O(n2ⁿ)的解数(2ⁿ)乘以成比例.

Answer 3

另一个简单的解决

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 4

没有递归的简单解决方案：

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 5

您可以使用以下内容轻松地从数组生成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数组.

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