Produit cartésien de plusieurs tableaux en JavaScript

Question

Comment implémenter le produit cartésien de plusieurs tableaux en JavaScript ?

A titre d'exemple,

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

devrait retourner

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

Answer 1

Voici une solution récursive simple et non fantaisiste :

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

Answer 2

Voici un exemple d'utilisation de l'ES2019 natif. flatMap . Aucune bibliothèque n'est nécessaire, il suffit d'un navigateur moderne (ou d'un transpondeur) :

data.reduce((a, b) => a.flatMap(x => b.map(y => [...x, y])), [[]]);

C'est essentiellement une version moderne de la réponse de Viebel, sans lodash.

Answer 3

Voici un moyen récursif qui utilise un ECMAScript 2015 fonction de générateur pour ne pas avoir à créer tous les tuples en même temps :

function* cartesian() {
    let arrays = arguments;
    function* doCartesian(i, prod) {
        if (i == arrays.length) {
            yield prod;
        } else {
            for (let j = 0; j < arrays[i].length; j++) {
                yield* doCartesian(i + 1, prod.concat([arrays[i][j]]));
            }
        }
    }
    yield* doCartesian(0, []);
}

console.log(JSON.stringify(Array.from(cartesian([1,2],[10,20],[100,200,300]))));
console.log(JSON.stringify(Array.from(cartesian([[1],[2]],[10,20],[100,200,300]))));

Answer 4

Il s'agit d'une solution purement ES6 utilisant fonctions de la flèche

function cartesianProduct(arr) {
  return arr.reduce((a, b) =>
    a.map(x => b.map(y => x.concat(y)))
    .reduce((a, b) => a.concat(b), []), [[]]);
}

var arr = [[1, 2], [10, 20], [100, 200, 300]];
console.log(JSON.stringify(cartesianProduct(arr)));

Answer 5

Utilisation d'un backtracking typique avec les générateurs ES6,

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(', ') + ']');
}

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

Vous trouverez ci-dessous une version similaire compatible avec les anciens navigateurs.

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(', ') + ']');
});

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