JavaScript – Générer des combinaisons à partir de n arrays avec m éléments

Voici un assez simple et court à l'aide d'une fonction d'assistant récursif:

 function cartesian() { var r = [], arg = arguments, max = arg.length-1; function helper(arr, i) { for (var j=0, l=arg[i].length; j<l; j++) { var a = arr.slice(0); // clone arr a.push(arg[i][j]); if (i==max) r.push(a); else helper(a, i+1); } } helper([], 0); return r; } 

Usage:

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

Pour que la fonction prenne un tableau de tableaux, il suffit de changer la signature pour la function cartesian(arg) afin que arg soit un paramètre au lieu de tous les arguments .

Après avoir fait une petite recherche, j'ai découvert une question antérieure: Trouver toutes les combinaisons de valeurs de matrice JavaScript

J'ai adapté un peu du code de là afin qu'il renvoie un tableau de tableaux contenant toutes les permutations:

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

J'ai mis une copie de travail à http://jsfiddle.net/7EakX/ qui prend le tableau que vous avez donné plus tôt ([[0,1], [0,1,2,3], [0,1,2] ]) Et envoie le résultat à la console du navigateur.

Juste pour le plaisir, voici une variante plus fonctionnelle de la solution dans ma première réponse:

 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<l; j++) { var a = arr.slice(); // clone arr a[i] = factor[j]; cont(a); } }; }, Array.prototype.push.bind(r))(new Array(args.length)); return r; } 

Alternativement, pour une vitesse maximale, nous pouvons compiler dynamiquement nos propres boucles:

 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<n; i++) { var arr = "$"+String.fromCharCode(97+i), ind = String.fromCharCode(105+i); args.push(arr); up += indent+"for (var "+ind+"=0, l"+arr+"="+arr+".length; "+ind+"<l"+arr+"; "+ind+"++) {\n"; down = indent+"}\n"+down; indent += " "; up += indent+"arr["+i+"] = "+arr+"["+ind+"];\n"; } var body = "var res=[],\n arr=[];\n"+up+indent+"res.push(arr.slice());\n"+down+"return res;"; return cartesian.cache[n] = new Function(args, body); } 

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

Voici une autre façon de le faire. Je traite les indices de tous les tableaux comme un nombre dont les chiffres sont tous des bases différentes (comme l'heure et les dates), en utilisant la longueur du tableau en tant que radix.

Ainsi, en utilisant votre premier ensemble de données, le premier chiffre est la base 2, le second est la base 4 et le troisième est la base 3. Le compteur commence 000, puis 001, 002, puis 010. Les chiffres correspondent aux indices dans le Les tableaux, et puisque l'ordre est conservé, ce n'est pas un problème.

J'ai un violon avec ça en train de travailler ici: http://jsfiddle.net/Rykus0/DS9Ea/1/

Et voici le code:

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

Je suggère une simple fonction de générateur récursif:

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