JavaScript – Gerando combinações de n arrays com m elementos

Estou tendo problemas para criar código para gerar combinações de um número n de matrizes com m número de elementos nelas, em JavaScript. Já vi perguntas semelhantes sobre isso para outros idiomas, mas as respostas incorporam magia sintática ou de biblioteca que não sei como traduzir.

Considere estes dados:

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

3 matrizes, com um número diferente de elementos nelas. O que eu quero fazer é obter todas as combinações combinando um item de cada matriz.

Por exemplo:

 0,0,0 // item 0 from array 0, item 0 from array 1, item 0 from array 2 0,0,1 0,0,2 0,1,0 0,1,1 0,1,2 0,2,0 0,2,1 0,2,2 

E assim por diante.

Se o número de matrizes fosse fixo, seria fácil fazer uma implementação codificada. Mas o número de matrizes pode variar:

 [[0,1], [0,1]] [[0,1,3,4], [0,1], [0], [0,1]] 

Qualquer ajuda seria muito apreciada.

    Aqui está um bastante simples e curto usando uma function auxiliar recursiva:

     function cartesian() { var r = [], arg = arguments, max = arg.length-1; function helper(arr, i) { for (var j=0, l=arg[i].length; j 

    Uso:

     cartesian([0,1], [0,1,2,3], [0,1,2]); 

    Para fazer com que a function receba um array de arrays, apenas mude a assinatura para function cartesian(arg) para que arg seja um parâmetro em vez de todos os arguments .

    Eu sugiro uma function geradora recursiva simples:

     // Generate all combinations of array elements: function* cartesian(head, ...tail) { let remainder = tail.length ? cartesian(...tail) : [[]]; for (let r of remainder) for (let h of head) yield [h, ...r]; } // Example: for (let c of cartesian([0,1], [0,1,2,3], [0,1,2])) { console.log(...c); } 

    Você poderia adotar uma abordagem iterativa criando sub arrays.

     var parts = [[0, 1], [0, 1, 2, 3], [0, 1, 2]], result = parts.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), [])); console.log(result.map(a => a.join(', '))); 
     .as-console-wrapper { max-height: 100% !important; top: 0; } 

    Depois de fazer uma pequena pesquisa, descobri uma questão relacionada anterior: Como encontrar todas as combinações de valores de matriz JavaScript

    Eu adaptei parte do código de lá para que ele retorne uma matriz de arrays contendo todas as permutações:

     function(arraysToCombine) { var divisors = []; for (var i = arraysToCombine.length - 1; i >= 0; i--) { divisors[i] = divisors[i + 1] ? divisors[i + 1] * arraysToCombine[i + 1].length : 1; } function getPermutation(n, arraysToCombine) { var result = [], curArray; for (var i = 0; i < arraysToCombine.length; i++) { curArray = arraysToCombine[i]; result.push(curArray[Math.floor(n / divisors[i]) % curArray.length]); } return result; } var numPerms = arraysToCombine[0].length; for(var i = 1; i < arraysToCombine.length; i++) { numPerms *= arraysToCombine[i].length; } var combinations = []; for(var i = 0; i < numPerms; i++) { combinations.push(getPermutation(i, arraysToCombine)); } return combinations; } 

    Eu coloquei uma cópia de trabalho em http://jsfiddle.net/7EakX/ que leva o array que você deu anteriormente ([[0,1], [0,1,2,3], [0,1,2] ]) e envia o resultado para o console do navegador.

    Apenas por diversão, aqui está uma variante mais funcional da solução na minha primeira resposta:

     function cartesian() { var r = [], args = Array.from(arguments); args.reduceRight(function(cont, factor, i) { return function(arr) { for (var j=0, l=factor.length; j 

    Alternativa, para velocidade total podemos compilar dinamicamente os nossos próprios loops:

     function cartesian() { return (cartesian.cache[arguments.length] || cartesian.compile(arguments.length)).apply(null, arguments); } cartesian.cache = []; cartesian.compile = function compile(n) { var args = [], indent = "", up = "", down = ""; for (var i=0; i 
     var f = function(arr){ if(typeof arr !== 'object'){ return false; } arr = arr.filter(function(elem){ return (elem !== null); }); // remove empty elements - make sure length is correct var len = arr.length; var nextPerm = function(){ // increase the counter(s) var i = 0; while(i < len) { arr[i].counter++; if(arr[i].counter >= arr[i].length){ arr[i].counter = 0; i++; }else{ return false; } } return true; }; var getPerm = function(){ // get the current permutation var perm_arr = []; for(var i = 0; i < len; i++) { perm_arr.push(arr[i][arr[i].counter]); } return perm_arr; }; var new_arr = []; for(var i = 0; i < len; i++) // set up a counter property inside the arrays { arr[i].counter = 0; } while(true) { new_arr.push(getPerm()); // add current permutation to the new array if(nextPerm() === true){ // get next permutation, if returns true, we got them all break; } } return new_arr; }; 

    Aqui está outra maneira de fazer isso. Eu trato os índices de todos os arrays como um número cujos dígitos são todos diferentes bases (como hora e datas), usando o comprimento do array como o radix.

    Assim, usando seu primeiro dataset, o primeiro dígito é a base 2, o segundo é a base 4 e o terceiro é a base 3. O contador começa em 000, depois em 001, 002 e em seguida em 010. Os dígitos correspondem a índices no matrizes, e desde que a ordem é preservada, isso não é problema.

    Eu tenho um violino com ele trabalhando aqui: http://jsfiddle.net/Rykus0/DS9Ea/1/

    e aqui está o código:

     // Arbitrary base x number class var BaseX = function(initRadix){ this.radix = initRadix ? initRadix : 1; this.value = 0; this.increment = function(){ return( (this.value = (this.value + 1) % this.radix) === 0); } } function combinations(input){ var output = [], // Array containing the resulting combinations counters = [], // Array of counters corresponding to our input arrays remainder = false, // Did adding one cause the previous digit to rollover? temp; // Holds one combination to be pushed into the output array // Initialize the counters for( var i = input.length-1; i >= 0; i-- ){ counters.unshift(new BaseX(input[i].length)); } // Get all possible combinations // Loop through until the first counter rolls over while( !remainder ){ temp = []; // Reset the temporary value collection array remainder = true; // Always increment the last array counter // Process each of the arrays for( i = input.length-1; i >= 0; i-- ){ temp.unshift(input[i][counters[i].value]); // Add this array's value to the result // If the counter to the right rolled over, increment this one. if( remainder ){ remainder = counters[i].increment(); } } output.push(temp); // Collect the results. } return output; } // Input is an array of arrays console.log(combinations([[0,1], [0,1,2,3], [0,1,2]])); 

    Outra implementação com estilo recursivo ES6

     Array.prototype.cartesian = function(a,...as){ return a ? this.reduce((p,c) => (p.push(...a.cartesian(...as).map(e => as.length ? [c,...e] : [c,e])),p),[]) : this; }; console.log(JSON.stringify([0,1].cartesian([0,1,2,3], [[0],[1],[2]])));