Produit cartésien de plusieurs tableaux en JavaScript

2017 mise à Jour: 2-ligne de la réponse à la vanille JS

Toutes les réponses ici sont trop compliqué, plus de 20 lignes de code ou même plus.

Cet exemple utilise seulement deux lignes de vanille JavaScript, pas de lodash, le trait de soulignement ou d'autres bibliothèques:

let f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesian = (a, b, ...c) => b ? cartesian(f(a, b), ...c) : a;

Mise à jour:

C'est le même que ci-dessus, mais l'amélioration de suivre strictement le Airbnb JavaScript Guide De Style validées à l'aide de ESLint avec eslint-config-airbnb-base:

const f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesian = (a, b, ...c) => (b ? cartesian(f(a, b), ...c) : a);

Un merci spécial à ZuBB pour me laisser savoir à propos de linter des problèmes avec le code d'origine.

Exemple

C'est exactement l'exemple de votre question:

let output = cartesian([1,2],[10,20],[100,200,300]);

Sortie

C'est la sortie de cette commande:

[ [ 1, 10, 100 ],
  [ 1, 10, 200 ],
  [ 1, 10, 300 ],
  [ 1, 20, 100 ],
  [ 1, 20, 200 ],
  [ 1, 20, 300 ],
  [ 2, 10, 100 ],
  [ 2, 10, 200 ],
  [ 2, 10, 300 ],
  [ 2, 20, 100 ],
  [ 2, 20, 200 ],
  [ 2, 20, 300 ] ]

Démo

Voir les démos sur:

• JS Bin avec Babel (pour les vieux navigateurs)
• JS Bin sans Babel (pour les navigateurs modernes)

Syntaxe

La syntaxe que j'ai utilisé ici n'est rien de nouveau.
Mon exemple utilise la propagation de l'opérateur et le reste des paramètres - les fonctionnalités de JavaScript définies dans la 6e édition de la norme ECMA-262 publiée en juin 2015 et s'est développée beaucoup plus tôt, mieux connu sous le nom ES6 ou ES2015. Voir:

• http://www.ecma-international.org/ecma-262/6.0/
• https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Functions/rest_parameters
• https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Operators/Spread_operator

Il rend le code comme ce si simple que c'est un péché de ne pas l'utiliser. Pour les anciennes plates-formes, qui ne prennent pas en charge en mode natif, vous pouvez toujours utiliser Babel ou d'autres outils pour transpile il à l'ancienne syntaxe - et, en fait, mon exemple transpiled par Babel est encore plus court et plus simple que la plupart des exemples ici, mais il n'a pas vraiment d'importance parce que la sortie de transpilation n'est pas quelque chose que vous avez besoin de comprendre ou de les maintenir, c'est juste un fait que je trouve intéressant.

Conclusion

Il n'y a pas besoin d'écrire des centaines de lignes de code qui est difficile à maintenir et il n'est pas nécessaire d'utiliser de bibliothèques entières, pour une chose si simple, lorsque deux lignes de vanille JavaScript peut facilement faire le travail. Comme vous pouvez le voir c'est vraiment rentable d'utiliser des fonctions de la langue et dans le cas où vous avez besoin de soutien archaïque plates-formes avec pas de support natif des fonctionnalités modernes, vous pouvez toujours utiliser Babel ou d'autres outils pour transpile la nouvelle syntaxe de l'ancien.

Ne pas un code comme il est 1995

JavaScript évolue et il le fait pour une raison. TC39 fait un travail incroyable de la langue de conception avec l'ajout de nouvelles fonctionnalités et le navigateur les fournisseurs font un travail remarquable de mise en œuvre de ces fonctionnalités.

Pour voir l'état actuel de la prise en charge native de toute fonction dans les navigateurs, voir:

• http://caniuse.com/
• https://kangax.github.io/compat-table/

De voir le soutien du Nœud versions, voir:

• http://node.green/

À utiliser la syntaxe moderne sur les plates-formes qui ne supportent pas nativement, l'utilisation Babel:

• https://babeljs.io/

il semble que la communauté pense de ce qui est insignifiant et ou facile de trouver une implémentation de référence, lors de la brève inspection, je ne pouvais pas ou peut-être c'est juste que j'aime ré-inventer la roue ou de la résolution de la salle de classe-comme les problèmes de programmation de toute façon c'est votre jour de chance:

function cartProd(paramArray) {

  function addTo(curr, args) {

    var i, copy, 
        rest = args.slice(1),
        last = !rest.length,
        result = [];

    for (i = 0; i < args[0].length; i++) {

      copy = curr.slice();
      copy.push(args[0][i]);

      if (last) {
        result.push(copy);

      } else {
        result = result.concat(addTo(copy, rest));
      }
    }

    return result;
  }


  return addTo([], Array.prototype.slice.call(arguments));
}


>> console.log(cartProd([1,2], [10,20], [100,200,300]));
>> [
     [1, 10, 100], [1, 10, 200], [1, 10, 300], [1, 20, 100], 
     [1, 20, 200], [1, 20, 300], [2, 10, 100], [2, 10, 200], 
     [2, 10, 300], [2, 20, 100], [2, 20, 200], [2, 20, 300]
   ]

référence complète de mise en œuvre qui est relativement efficace... 😀

sur l'efficacité: vous pourriez gagner quelques en prenant le cas de la boucle et avoir 2 boucles séparées, car il est techniquement constante et vous aurait aider avec la direction de la prévision et de tout ce gâchis, mais ce point est une sorte de plaidoirie en javascript

anywho, profitez -ck

Voici un non-fantaisie, simple solution récursive:

JS:

function cartesianProduct(a) { //a = array of array
    var i, j, l, m, a1, o = [];
    if (!a || a.length == 0) return a;

    a1 = a.splice(0, 1)[0]; //the first array of a
    a = cartesianProduct(a);
    for (i = 0, l = a1.length; i < l; i++) {
        if (a && a.length) for (j = 0, m = a.length; j < m; j++)
            o.push([a1[i]].concat(a[j]));
        else
            o.push([a1[i]]);
    }
    return o;
}

console.log(cartesianProduct([[1,2], [10,20], [100,200,300]]));
//[[1,10,100],[1,10,200],[1,10,300],[1,20,100],[1,20,200],[1,20,300],[2,10,100],[2,10,200],[2,10,300],[2,20,100],[2,20,200],[2,20,300]]

À l'aide d'un typique retour en arrière avec ES6 générateurs,

JS:

function cartesianProduct(...arrays) {
  let current = new Array(arrays.length);
  return (function* backtracking(index) {
    if(index == arrays.length) yield current.slice();
    else for(let num of arrays[index]) {
      current[index] = num;
      yield* backtracking(index+1);
    }
  })(0);
}
for (let item of cartesianProduct([1,2],[10,20],[100,200,300])) {
  console.log('[' + item.join(', ') + ']');
}

CSS:

div.as-console-wrapper { max-height: 100%; }

Ci-dessous il y a une version similaire compatible avec les anciens navigateurs.

JS:

function cartesianProduct(arrays) {
  var result = [],
      current = new Array(arrays.length);
  (function backtracking(index) {
    if(index == arrays.length) return result.push(current.slice());
    for(var i=0; i<arrays[index].length; ++i) {
      current[index] = arrays[index][i];
      backtracking(index+1);
    }
  })(0);
  return result;
}
cartesianProduct([[1,2],[10,20],[100,200,300]]).forEach(function(item) {
  console.log('[' + item.join(', ') + ']');
});

CSS:

div.as-console-wrapper { max-height: 100%; }

Un coffeescript version avec lodash:

_ = require("lodash")
cartesianProduct = ->
    return _.reduceRight(arguments, (a,b) ->
        _.flatten(_.map(a,(x) -> _.map b, (y) -> x.concat(y)), true)
    , [ [] ])

C'est taggés fonctionnelle de la programmation donc, nous allons jeter un oeil à la Liste monade:

Une demande pour ce monadique de la liste est le représentant de calcul non déterministe. List peut contenir les résultats pour tous les chemins d'exécution dans un algorithme...

Bien que cela sonne comme un parfait ajustement pour cartesian. JavaScript nous donne Array et la monadique la fonction de liaison est Array.prototype.flatMap, nous allons donc mettre à utiliser -

JS:

const cartesian = (...all) =>
{ const loop = (t, a, ...more) =>
    a === undefined
      ? [ t ]
      : a .flatMap (x => loop ([ ...t, x ], ...more))
  return loop ([], ...all)
}

console .log (cartesian ([1,2], [10,20], [100,200,300]))

Au lieu de loop ci-dessus, t peut être ajouté comme un curry de paramètre -

JS:

const makeCartesian = (t = []) => (a, ...more) =>
  a === undefined
    ? [ t ]
    : a .flatMap (x => makeCartesian ([ ...t, x ]) (...more))

const cartesian =
  makeCartesian ()

console .log (cartesian ([1,2], [10,20], [100,200,300]))

Dans mon contexte particulier, la "vieille" approche semble être plus efficace que les méthodes basées sur des plus modernes. Ci-dessous est le code (y compris une petite comparaison avec d'autres solutions postées dans ce fil par @rsp et @sebnukem) doit-elle s'avérer utile à quelqu'un d'autre aussi.

L'idée est la suivante. Disons que nous construisons le produit extérieur de N tableaux, a_1,...,a_N dont chacune a m_i composants. Le produit extérieur de ces tableaux a M=m_1*m_2*...*m_N éléments et nous pouvons identifier chacun d'eux avec une N-dimensions vecteur dont les composantes sont des nombres entiers positifs et i-ème composante est strictement bornée par m_i. Par exemple, le vecteur (0, 0, ..., 0) correspond à la combinaison particulière au sein de laquelle on prend le premier élément de chaque tableau, alors que (m_1-1, m_2-1, ..., m_N-1) est identifié avec la combinaison où l'on prend le dernier élément de chaque tableau. Ainsi, pour construire tous les M combinaisons, la fonction ci-dessous consécutivement construit toutes ces vecteurs et pour chacun d'entre eux identifie le correspondant de la combinaison des éléments de la saisie des tableaux.

function cartesianProduct(){
const N = arguments.length;
var arr_lengths = Array(N);
var digits = Array(N);
var num_tot = 1;
for(var i = 0; i < N; ++i){
const len = arguments[i].length;
if(!len){
num_tot = 0;
break;
}
digits[i] = 0;
num_tot *= (arr_lengths[i] = len);
}
var ret = Array(num_tot);
for(var num = 0; num < num_tot; ++num){
var item = Array(N);
for(var j = 0; j < N; ++j){ item[j] = arguments[j][digits[j]]; }
ret[num] = item;
for(var idx = 0; idx < N; ++idx){
if(digits[idx] == arr_lengths[idx]-1){
digits[idx] = 0;
}else{
digits[idx] += 1;
break;
}
}
}
return ret;
}
//------------------------------------------------------------------------------
let _f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesianProduct_rsp = (a, b, ...c) => b ? cartesianProduct_rsp(_f(a, b), ...c) : a;
//------------------------------------------------------------------------------
function cartesianProduct_sebnukem(a) {
var i, j, l, m, a1, o = [];
if (!a || a.length == 0) return a;
a1 = a.splice(0, 1)[0];
a = cartesianProduct_sebnukem(a);
for (i = 0, l = a1.length; i < l; i++) {
if (a && a.length) for (j = 0, m = a.length; j < m; j++)
o.push([a1[i]].concat(a[j]));
else
o.push([a1[i]]);
}
return o;
}
//------------------------------------------------------------------------------
const L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const args = [L, L, L, L, L, L];
let fns = {
'cartesianProduct': function(args){ return cartesianProduct(...args); },
'cartesianProduct_rsp': function(args){ return cartesianProduct_rsp(...args); },
'cartesianProduct_sebnukem': function(args){ return cartesianProduct_sebnukem(args); }
};
Object.keys(fns).forEach(fname => {
console.time(fname);
const ret = fns[fname](args);
console.timeEnd(fname);
});

avec node v6.12.2, je reçois suivantes horaires:

cartesianProduct: 427.378ms
cartesianProduct_rsp: 1710.829ms
cartesianProduct_sebnukem: 593.351ms

Juste pour un choix d'une réelle simplicité de mise en oeuvre à l'aide de la matrice de reduce:

const array1 = ["day", "month", "year", "time"];
const array2 = ["from", "to"];
const process = (one, two) => [one, two].join(" ");
const product = array1.reduce((result, one) => result.concat(array2.map(two => process(one, two))), []);

Pour ceux qui les besoins de la Machine (réimplémentée @Danny réponse)

/**
* Calculates "Cartesian Product" sets.
* @example
*   cartesianProduct([[1,2], [4,8], [16,32]])
*   Returns:
*   [
*     [1, 4, 16],
*     [1, 4, 32],
*     [1, 8, 16],
*     [1, 8, 32],
*     [2, 4, 16],
*     [2, 4, 32],
*     [2, 8, 16],
*     [2, 8, 32]
*   ]
* @see https://stackoverflow.com/a/36234242/1955709
* @see https://en.wikipedia.org/wiki/Cartesian_product
* @param arr {T[][]}
* @returns {T[][]}
*/
function cartesianProduct<T> (arr: T[][]): T[][] {
return arr.reduce((a, b) => {
return a.map(x => {
return b.map(y => {
return x.concat(y)
})
}).reduce((c, d) => c.concat(d), [])
}, [[]] as T[][])
}

Plaine JS approche par force brute qui prend un tableau de tableaux en entrée.

var cartesian = function(arrays) {
var product = [];
var precals = [];
var length = arrays.reduce(function(acc, curr) {
return acc * curr.length
}, 1);
for (var i = 0; i < arrays.length; i++) {
var array = arrays[i];
var mod = array.length;
var div = i > 0 ? precals[i - 1].div * precals[i - 1].mod : 1;
precals.push({
div: div,
mod: mod
});
}
for (var j = 0; j < length; j++) {
var item = [];
for (var i = 0; i < arrays.length; i++) {
var array = arrays[i];
var precal = precals[i];
var k = (~~(j / precal.div)) % precal.mod;
item.push(array[k]);
}
product.push(item);
}
return product;
};
cartesian([
[1],
[2, 3]
]);
cartesian([
[1],
[2, 3],
[4, 5, 6]
]);

JS:

var chars = ['A', 'B', 'C']
var nums = [1, 2, 3]
var cartesianProduct = function() {
return _.reduce(arguments, function(a, b) {
return _.flatten(_.map(a, function(x) {
return _.map(b, function(y) {
return x.concat(y);
});
}), true);
}, [
[]
]);
};
console.log(cartesianProduct(chars, nums))

HTML:

<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>

Juste converti @dummersl de l' réponse de CoffeScript de JavaScript. Il fonctionne, tout simplement.

var chars = ['A', 'B', 'C']
var nums = [1, 2, 3]
var cartesianProduct = function() {
return _.reduce(arguments, function(a, b) {
return _.flatten(_.map(a, function(x) {
return _.map(b, function(y) {
return x.concat(y);
});
}), true);
}, [[]]);
};
console.log( cartesianProduct(chars, nums) )

Pas de bibliothèques nécessaires! 🙂

Besoins flèche fonctions et probablement pas très efficace. :/

JS:

const flatten = (xs) => 
xs.flat(Infinity)
const binaryCartesianProduct = (xs, ys) =>
xs.map((xi) => ys.map((yi) => [xi, yi])).flat()
const cartesianProduct = (...xss) =>
xss.reduce(binaryCartesianProduct, [[]]).map(flatten)
console.log(cartesianProduct([1,2,3], [1,2,3], [1,2,3]))