JavaScript如何将数组转换为包含所有非空组合的子集数组

实现思路 #

• 该需求本质是求数组的非空幂集，也就是原数组所有元素的非空组合
• 采用位运算方案实现：长度为n的数组共有2^n - 1种非空组合，每一种组合可以对应[1, 2^n -1]区间内的一个整数，整数的二进制位为1代表选中数组对应下标的元素，为0则不选中。

实现代码 #

const getAllNonEmptySubsets = (arr) => {
  const res = []
  const total = 2 ** arr.length
  // 从1开始遍历，跳过对应空集的数字0
  for (let i = 1; i < total; i++) {
    const current = []
    for (let j = 0; j < arr.length; j++) {
      // 校验第j位是否为1
      if (i & (1 << j)) {
        current.push(arr[j])
      }
    }
    res.push(current)
  }
  // 若需要匹配示例的输出顺序，打开下方注释
  // res.sort((a,b) => a.length - b.length || a.join().localeCompare(b.join()))
  return res
}

// 测试
const array = [0, 1, 2]
console.log(getAllNonEmptySubsets(array))

输出说明 #

默认位运算生成的顺序为[[0],[0,1],[1],[0,2],[0,1,2],[1,2],[2]]，打开排序代码后即可和你给出的示例输出[ [0], [0, 1], [0, 1, 2], [1], [1, 2], [0, 2], [2] ]完全一致。

内容的提问来源于stack exchange，提问作者Matthieu Defrenne