找到阵列中所有可能的子集组合？

Question

我需要获得一个数组的所有可能子集,其中包含最少2个项目和未知最大值.有人可以帮我一点吗？

说我有这个......

[1,2,3]

......我怎么得到这个？

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

Answer 1

窃取此 JavaScript组合生成器后,我添加了一个参数来提供最小长度,

var combine = function(a, min) {
    var fn = function(n, src, got, all) {
        if (n == 0) {
            if (got.length > 0) {
                all[all.length] = got;
            }
            return;
        }
        for (var j = 0; j < src.length; j++) {
            fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
        }
        return;
    }
    var all = [];
    for (var i = min; i < a.length; i++) {
        fn(i, a, [], all);
    }
    all.push(a);
    return all;
}

要使用,提供一个数组,以及所需的最小子集长度,

var subsets = combine([1, 2, 3], 2);

输出是,

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

Answer 2

通过这个问题的小调整,我希望我的解决方案更有效,因为它使用位运算符来生成所有子集.

var sets = (function(input, size) {
    var results = [], result, mask, i, total = Math.pow(2, input.length);
    for (mask = size; mask < total; mask++) {
        result = [];
        i = input.length - 1;

        do {
            if ((mask & (1 << i)) !== 0) {
                result.push(input[i]);
            }
        } while (i--);

        if (result.length >= size) {
            results.push(result);
        }
    }

    return results; 
})(['a','b','c','d','e','f'], 2);
console.log(sets);

Answer 3

以下是使用ECMAScript 2015 生成器函数查找所有组合的方法:

function* generateCombinations(arr) {
  function* doGenerateCombinations(offset, combo) {
    yield combo;
    for (let i = offset; i < arr.length; i++) {
      yield* doGenerateCombinations(i + 1, combo.concat(arr[i]));
    }
  }
  yield* doGenerateCombinations(0, []);
}

for (let combo of generateCombinations([1, 2, 3, 4, 5])) {
  console.log(JSON.stringify(combo));
}

要限制问题中要求的最小尺寸,只需确保组合的长度,然后再产生它:

function* generateCombinations(arr, minSize) {
  function* doGenerateCombinations(offset, combo) {
    if (combo.length >= minSize) {
      yield combo;
    }
    for (let i = offset; i < arr.length; i++) {
      yield* doGenerateCombinations(i + 1, combo.concat(arr[i]));
    }
  }
  yield* doGenerateCombinations(0, []);
}

for (let combo of generateCombinations([1, 2, 3, 4, 5], 2)) {
  console.log(JSON.stringify(combo));
}

限制点yield允许以可读方式使该功能适应其他常见用例,例如,选择精确大小的所有组合:

function* generateCombinations(arr, size) {
  function* doGenerateCombinations(offset, combo) {
    if (combo.length == size) {
      yield combo;
    } else {
      for (let i = offset; i < arr.length; i++) {
        yield* doGenerateCombinations(i + 1, combo.concat(arr[i]));
      }
    }
  }
  yield* doGenerateCombinations(0, []);
}

for (let combo of generateCombinations([1, 2, 3, 4, 5], 2)) {
  console.log(JSON.stringify(combo));
}

Answer 4

这个算法要求递归......这就是我要做的

var arr = [1,2,3,4,5];
function getSubArrays(arr){
  if (arr.length === 1) return [arr];
  else {
  	subarr = getSubArrays(arr.slice(1));
  	return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]);
  }
}
console.log(JSON.stringify(getSubArrays(arr)));

上述算法的另一个奇特版本;

var arr = [1,2,3,4,5],
    sas = ([n,...ns],sa) => !ns.length ? [[n]]
                                       : (sa = sas(ns),
                                          sa.concat(sa.map(e => e.concat(n)),[[n]]));

为了解最新情况,我们一步一步走

• 直到我们最终得到一个长度为1的数组作为参数,我们继续getSubArrays使用参数数组的尾部调用相同的函数.所以尾巴[1,2,3,4,5]是[2,3,4,5].
• 一旦我们将单个项数组作为参数,例如[5]我们返回[[5]]上一个getSubArrays函数调用.
• 然后在前面的getSubArrays功能arr是[4,5]和subarr被分配到[[5]].
• 现在我们返回[[5]].concat([[5]].map(e => e.concat(4), [[4]])实际上[[5], [5,4], [4]]到前一个getSubArrays函数调用.
• 然后在前面的getSubArrays功能arr是[3,4,5]和subarr被分配到[[5], [5,4], [4]].
• 等等...

Answer 5

组合,简短的一个:

function combinations(array) {
    return new Array(1 << array.length).fill().map(
        (e1,i) => array.filter((e2, j) => i & 1 << j));
}

并打电话给

combinations([1,2,3]).filter(a => a.length >= 2)