Javascript 在数组中找到所有可能的子集组合？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5752002/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-08-23 18:42:23 来源:igfitidea点击:
Find all possible subset combos in an array?
提问by Stephen Belanger
I need to get all possible subsets of an array with a minimum of 2 items and an unknown maximum. Anyone that can help me out a bit?
我需要获得一个数组的所有可能子集，最少有 2 个项目，最大值未知。有谁能帮我一下吗？
Say I have this...
说我有这个...
[1,2,3]
...how do I get this?
……我怎么得到这个？
[
[1,2]
, [1,3]
, [2,3]
, [1,2,3]
]
回答by Anurag
After stealing thisJavaScript combination generator, I added a parameter to supply the minimum length resulting in,
在窃取了这个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;
}
To use, supply an array, and the minimum subset length desired,
要使用，请提供一个数组和所需的最小子集长度，
var subsets = combine([1, 2, 3], 2);
Output is,
输出是，
[[1, 2], [1, 3], [2, 3], [1, 2, 3]]
回答by Dewey
With a small tweak from this question, I hope my solution is more efficient because it uses bit operator to generate all the subsets.
通过这个问题的一个小调整，我希望我的解决方案更有效，因为它使用位运算符来生成所有子集。
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);
回答by heenenee
Here is a way to find all combinations using ECMAScript 2015 generator function:
这是使用 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));
}To restrict to a minimum size as requested in the question, simply ensure the length of the combination before yielding it:
要限制为问题中要求的最小尺寸，只需在产生组合之前确保组合的长度：
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));
}Restricting at the point of yieldallows a readable way to adapt this function to other common use cases, e.g., to choose all combinations of an exact size:
在点上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));
}回答by zovio
Combinations, short one:
组合，简短的一个：
function combinations(array) {
return new Array(1 << array.length).fill().map(
(e1,i) => array.filter((e2, j) => i & 1 << j));
}
And call as
并称为
combinations([1,2,3]).filter(a => a.length >= 2)
回答by Redu
This algorithm cries for recursion... this is how i would do it
这个算法要求递归......这就是我要做的
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)));Another fancy version of the above algorithm;
上述算法的另一个奇特版本；
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]]));
In order to understand whats going on lets go step by step
为了了解发生了什么让我们一步一步
- Up until we end up with an array of length 1 as argument we keep calling the same
getSubArraysfunction with the tailof the argument array. So tail of[1,2,3,4,5]is[2,3,4,5]. - Once we have a single item array as argument such as
[5]we return[[5]]to the previousgetSubArraysfunction call. - Then in the previous
getSubArraysfunctionarris[4,5]andsubarrgets assigned to[[5]]. - Now we return
[[5]].concat([[5]].map(e => e.concat(4), [[4]])which is in fact[[5], [5,4], [4]]to the to the previousgetSubArraysfunction call. - Then in the previous
getSubArraysfunctionarris[3,4,5]andsubarrgets assigned to[[5], [5,4], [4]]. - and so on...
- 直到我们最终得到一个长度为 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]]。 - 等等...
回答by Darshan
Using binary numbers
使用二进制数
// 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);
回答by bob
If element order is important:
如果元素顺序很重要：
// same values, different order:
[1,2]
[2,1]
[1,3]
[3,1]
Then you may also want to consider a permutation.
那么您可能还需要考虑排列。
// ---------------------
// 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() + "]");
}
BE WARNED !!! - Your machine can't handle arrays with >10 items.
被警告 ！！！- 您的机器无法处理超过 10 个项目的数组。
- If your array has 9 items, there are nearly 1 million combinations.
- If your array has 12 items, there are over 1 billion combinations.
- If your array has 15 items, there are over 3 trillion combinations.
- If your array has 18 items, there are over 17 quadrillion combinations.
- If your array has 20 items, there are over 6 quintillion combinations.
- If your array has 21 items, there are over 138 sextillion combinations.
- If your array has 22 items, there are over 3 zillion combinations.
- 如果您的数组有 9 个项目，则有近 100 万种组合。
- 如果您的数组有 12 个项目，则有超过 10 亿种组合。
- 如果您的阵列有 15 个项目，则有超过 3 万亿个组合。
- 如果您的阵列有 18 个项目，则有超过 17 千万个组合。
- 如果您的阵列有 20 个项目，则有超过 6 个 quintillion 组合。
- 如果您的数组有 21 个项目，则有超过 138 种六百个组合。
- 如果您的阵列有 22 个项目，则有超过 3 种组合。
回答by Meeting Attender
I've modified the accepted solution a little bit to consider the empty set when min is equal to 0 (empty set is a subset of any given set).
我稍微修改了接受的解决方案，以考虑当 min 等于 0 时的空集（空集是任何给定集的子集）。
Here is a full sample page to copy paste, ready to run with some output.
这是复制粘贴的完整示例页面，准备好运行一些输出。
<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 ? '<E>' : inArr[j];
csv += ']';
if(i < arr.length - 1)
csv += ' ';
}
csv += ' (# 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>
