在数组中找到所有可能的子集组合？

Question

我需要获取一个数组的所有可能子集，其中至少有2个元素且数量未知。有谁能帮帮我吗？

假设我有以下数组：

[1, 2, 3]

我该如何获得这个东西？

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

- Stephen Belanger

---

所以基本上你想要幂集，减去那些只有 <2 个项的集合？ - Josh Leitzel

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

- Anurag

---

当我合并30个数字时，应用程序会崩溃。 - user5738822

这似乎缺少空集。 - terary

Answer 2

组合，简称：

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

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

- zovio

---

不错，但它是一个算法，所以比你写的那些话更需要一些措辞 :) 不需要太多，只需要一个简短的摘要来给它一些背景。 - user3658510

"fill（）"需要至少一个值...这样不起作用。 - Jonathan

这很好阅读，但会生成一个空值（结果中的第一个数组）！ - Sampgun

Answer 3

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

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

- Dewey

---

如果只想要特定大小的子集怎么办？一个选择是将 if(result.length >= size) 更改为 if(result.length === size)。但这似乎效率低下，因为它仍然会产生所有2^n个子集，然后丢弃那些错误大小的子集。你的代码能否进一步调整以专注于一个特定的大小呢？ - Gabe Conant

结果是反向的，因为使用了逆向while循环。如果使用正向循环，则会有正确的顺序。 - megawac

这是一个不错的解决方案，但一旦您的数组达到任何大于16个字符的独特组合，它就会崩溃。 - mjwrazor

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函数并传入参数数组的tail。因此，[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]])返回到之前的getSubArrays函数调用中，这实际上是[[5], [5,4], [4]]。
• 然后，在之前的getSubArrays函数中，arr为[3,4,5]，而subarr则被赋值为[[5], [5,4], [4]]。
• 以此类推...

- Redu

---

运行这段代码后，我可以确定它给我提供了我想要的答案，而且我喜欢它使用了递归。但是我有些难以理解。@Redu 你能否解释一下你是如何得出这种方法的呢？ - user3295436

@user3295436 谢谢。更现代化的同一算法版本和解释已添加到答案中。 - Redu

Answer 5

以下是一种使用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的点上限制允许一种可读的方式来适应此函数到其他常见用例，例如选择所有精确大小的组合：

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

- heenenee

---

我正在使用您的方法，但在尝试对非常大的输入进行操作时，该函数会超时。这是因为我们首先生成所有可能的组合，然后产生每个组合。我们该如何修改此函数以使其更有效？以下是该函数的链接和挑战描述：https://repl.it/E2QW/1 - Piotr Berebecki

@PiotrBerebecki 看起来你需要在你的for循环周围加上一个else。 - heenenee

谢谢，我会尝试测试它并让您知道结果。 - Piotr Berebecki

我仍在努力理解这个答案，但我真的很喜欢这段代码。 - Hinrich

Answer 6

使用二进制数

// eg. [2,4,5] ==> {[],[2],[4],[5],[2,4],[4,5],[2,5], [2,4,5]}

var a = [2, 4, 5], res = [];
for (var i = 0; i < Math.pow(2, a.length); i++) {
    var bin = (i).toString(2), set = [];
    bin = new Array((a.length-bin.length)+1).join("0")+bin;
    console.log(bin);
    for (var j = 0; j < bin.length; j++) {
        if (bin[j] === "1") {
            set.push(a[j]);
        }
    }
    res.push(set);
}
console.table(res);

- Darshan

Answer 7

这种方法可能会或可能不会很好地进行基准测试，但它是另一种方法，而且相当简洁。

const combinations = arr => arr.reduce((acc, item) => {
  return acc.concat(acc.map(x => [...x, item]));
}, [[]]);


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

- BobRodes

Answer 8

我稍微修改了已接受的解决方案，以考虑当最小值为0时空集合（空集是任何给定集合的子集）。

这里是一个完整的示例页面，可以复制粘贴，准备好运行并输出一些结果。

<html>

<head>

<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>All Subsets</title>

<script type="text/javascript">

// get all possible subsets of an array with a minimum of X (min) items and an unknown maximum
var FindAllSubsets = 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 = [];

    // empty set is a subset of the set (only when min number of elements can be 0)
    if(min == 0)
      all.push([-1]); // array with single element '-1' denotes empty set

    for (var i = min; i < a.length; i++) {
        fn(i, a, [], all);
    }

    all.push(a);
    return all;
}

function CreateInputList(){
  var inputArr = [];
  var inputArrSize = 4;
  var maxInputValue = 10;
  for(i=0; i < inputArrSize; i++){
    var elem = Math.floor(Math.random()*maxInputValue);
    // make sure to have unique elements in the array
    while(inputArr.contains(elem)){ // OR - while(inputArr.indexOf(elem) > -1){
      elem = Math.floor(Math.random()*maxInputValue);
    }
    inputArr.push(elem);
  }
  return inputArr;
}

Array.prototype.contains = function(obj) {
    var i = this.length;
    while (i--) {
        if (this[i] === obj) {
            return true;
        }
    }
    return false;
}

function ArrayPrinter(arr){
  var csv = 'input = [';
  var i = 0;
  for(i; i<arr.length - 1; i++){
    csv += arr[i] + ', ';
  }
  csv += arr[i];

  var divResult = document.getElementById('divResult');
  divResult.innerHTML += csv + ']<br />';
}

// assumes inner array with single element being '-1' an empty set
function ArrayOfArraysPrinter(arr){
  var csv = 'subsets = ';
  var i = 0;
  for(i; i<arr.length; i++){
    csv += '[';
    var j = 0;
    var inArr = arr[i];
    for(j; j<inArr.length - 1; j++){
      csv += inArr[j] + ', ';
    }
    // array with single element '-1' denotes empty set
    csv += inArr[j] == -1 ? '&lt;E&gt;' : inArr[j];
    csv += ']';
    if(i < arr.length - 1)
      csv += '&nbsp;&nbsp;';
  }

  csv += ' &nbsp; (&#35; of subsets =' + arr.length + ')';

  var divResult = document.getElementById('divResult');
  divResult.innerHTML += csv + '<br />';
}

function Main(){
  // clear output
  document.getElementById('divResult').innerHTML = '';

  // sample run (min = 0)
  document.getElementById('divResult').innerHTML += '<hr/>MIN = 0 (must include empty set)<br />';
  var list = CreateInputList();
  ArrayPrinter(list);
  var subsets = FindAllSubsets(list, 0);
  ArrayOfArraysPrinter(subsets);
  document.getElementById('divResult').innerHTML += '<hr />';

  // sample run (min = 1)
  document.getElementById('divResult').innerHTML += 'MIN = 1<br />'; 
  var list = CreateInputList();
  ArrayPrinter(list);
  var subsets = FindAllSubsets(list, 1);
  ArrayOfArraysPrinter(subsets);
  document.getElementById('divResult').innerHTML += '<hr />';

  // sample run (min = 2)
  document.getElementById('divResult').innerHTML += 'MIN = 2<br />'; 
  var list = CreateInputList();
  ArrayPrinter(list);
  var subsets = FindAllSubsets(list, 2);
  ArrayOfArraysPrinter(subsets);
  document.getElementById('divResult').innerHTML += '<hr />';

  // sample run (min = 3)
  document.getElementById('divResult').innerHTML += 'MIN = 3<br />'; 
  var list = CreateInputList();
  ArrayPrinter(list);
  var subsets = FindAllSubsets(list, 3);
  ArrayOfArraysPrinter(subsets);
  document.getElementById('divResult').innerHTML += '<hr />';

  // sample run (min = 4)
  document.getElementById('divResult').innerHTML += 'MIN = 4<br />'; 
  var list = CreateInputList();
  ArrayPrinter(list);
  var subsets = FindAllSubsets(list, 4);
  ArrayOfArraysPrinter(subsets);
  document.getElementById('divResult').innerHTML += '<hr />';
}

</script>

</head>

<body>
  <input type="button" value="All Subsets" onclick="Main()" />
  <br />
  <br />
  <div id="divResult"></div>
</body>

</html>

- Meeting Attender

---

我明白你的意思，放心吧 :) - LOAS

感谢您修复了一个不公平的情况，家人 ;) - Meeting Attender

Answer 9

如果元素顺序很重要：

// same values, different order:

[1,2]
[2,1]

[1,3]
[3,1]

那么您可能还想考虑一下排列。

// ---------------------
// Permutation
// ---------------------
function permutate (src, minLen, maxLen){

    minLen = minLen-1 || 0;
    maxLen = maxLen || src.length+1;
    var Asource = src.slice(); // copy the original so we don't apply results to the original.

    var Aout = [];

    var minMax = function(arr){
        var len = arr.length;
        if(len > minLen && len <= maxLen){
            Aout.push(arr);
        }
    }

    var picker = function (arr, holder, collect) {
        if (holder.length) {
           collect.push(holder);
        }
        var len = arr.length;
        for (var i=0; i<len; i++) {
            var arrcopy = arr.slice();
            var elem = arrcopy.splice(i, 1);
            var result = holder.concat(elem);
            minMax(result);
            if (len) {
                picker(arrcopy, result, collect);
            } else {
                collect.push(result);
            }
        }   
    }

    picker(Asource, [], []);

    return Aout;

}

var combos = permutate(["a", "b", "c"], 2);


for(var i=0; i<combos.length; i++){
    var item = combos[i];
    console.log("combos[" + i + "]" + " = [" + item.toString() + "]");
}

警告！- 您的计算机无法处理超过10个项目的数组。

• 如果您的数组有9个项目，则有近100万种组合。
• 如果您的数组有12个项目，则有超过10亿种组合。
• 如果您的数组有15个项目，则有超过3万亿种组合。
• 如果您的数组有18个项目，则有超过17千万亿种组合。
• 如果您的数组有20个项目，则有超过6百万亿种组合。
• 如果您的数组有21个项目，则有超过138百万亿种组合。
• 如果您的数组有22个项目，则有超过3千亿亿种组合。

- bob

---

问题要求组合，而不是排列。 - River Tam

据我理解，排列是推导出所有可能组合的（唯一？）方法。 - bob

我认为那是不正确的。创建一个大小相同、填充布尔值的不同数组。遍历该数组的所有可能性（每个布尔值都可以是真或假），并且对于每个可能性，将每个“真”对应的值添加到一个集合中。这将创建2^n中的所有组合，但它不会创建所有排列。你也没有描述从排列集合中提取组合的过程，只是一种创建大量排列的方法。 - River Tam

是的，你说得对，我曾经认为元素顺序也起到了作用。（就像有人想要锁定组合而不是唯一值集一样思考。）排列考虑元素顺序，而组合只寻求唯一集合。因此，如果从排列返回的集合被排序（单独地），将会有许多相同的结果。所以现在我的理解更好了。 - bob

Answer 10

第一次提交答案！希望能对某人有所帮助。我用这个类似的递归解决方案来返回一个数组的数组，我发现flatMap()方法非常有用。

var arr = [1,2,3,4,5];

function getAllCombos(arr){
   if(arr[0] === undefined) return [arr]
   return getAllCombos(arr.slice(1)).flatMap(el => [el.concat(arr[0]), el])
}
console.log(JSON.stringify(getAllCombos(arr)));

如果你想让console.log()输出以[1, 2, 3, 4 , 5]开头而不是[5, 4, 3, 2, 1]，你可以像这样添加sort()方法：

var arr = [1,2,3,4,5];

function getAllCombos(arr){
   if(arr[0] === undefined) return [arr]
   return getAllCombos(arr.slice(1)).flatMap(el => [el.concat(arr[0]).sort(), el])
}
console.log(JSON.stringify(getAllCombos(arr)));

- Sector88