Encontre todos os possíveis combos de subconjunto em uma matriz?

Eu preciso obter todos os subconjuntos possíveis de uma matriz com um mínimo de 2 itens e um máximo desconhecido. Alguém que possa me ajudar um pouco?

Diga que eu tenho isso …

[1,2,3] 

… como eu obtenho isso?

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

Depois de roubar esse gerador de combinação de JavaScript, adicionei um parâmetro para fornecer o comprimento mínimo resultante,

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

Para usar, forneça uma matriz e o comprimento mínimo do subconjunto desejado,

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

Saída é,

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

Com um pequeno ajuste desta questão , espero que minha solução seja mais eficiente, pois usa o operador bit para gerar todos os subconjuntos.

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

Aqui está uma maneira de encontrar todas as combinações usando a function de gerador 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)); } 

Combinações, uma curta:

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

E chame como

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

Este algoritmo chora por recursion … é assim que eu faria

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

Usando números binários

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

Se a ordem dos elementos é importante:

 // same values, different order: [1,2] [2,1] [1,3] [3,1] 

Então você também pode querer considerar uma permutação.

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

ESTEJA AVISADO !!! - Sua máquina não pode lidar com matrizes com> 10 itens.

  • Se sua matriz tiver 9 itens, existem quase 1 milhão de combinações.
  • Se sua matriz tiver 12 itens, haverá mais de 1 bilhão de combinações.
  • Se sua matriz tiver 15 itens, haverá mais de 3 trilhões de combinações.
  • Se sua matriz tiver 18 itens, haverá mais de 17 quadrilhões de combinações.
  • Se sua matriz tiver 20 itens, haverá mais de 6 combinações de quintilhões.
  • Se o seu array tiver 21 itens, existem mais de 138 combinações de sextillions.
  • Se sua matriz tiver 22 itens, haverá mais de três zilhões de combinações.

Eu modifiquei a solução aceita um pouco para considerar o conjunto vazio quando min é igual a 0 (conjunto vazio é um subconjunto de qualquer conjunto dado).

Aqui está uma página de amostra completa para copiar e colar, pronta para ser executada com alguma saída.

    All Subsets