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 ligne unique récursive qui fonctionne en utilisant seulement flatMap et map :

const inp = [
  [1, 2],
  [10, 20],
  [100, 200, 300]
];

const cartesian = (first, ...rest) => 
  rest.length ? first.flatMap(v => cartesian(...rest).map(c => [v].concat(c))) 
              : first;

console.log(cartesian(...inp));

Answer 2

Quelques-unes des réponses de ce sujet échouent lorsque l'un des tableaux d'entrée contient un élément de tableau. Vous devriez vérifier cela.

De toute façon, il n'y a pas besoin d'underscore, de lodash ou autre. Je crois que celui-ci devrait le faire avec du pur JS ES6, aussi fonctionnel que possible.

Ce morceau de code utilise un reduce et un nested map, simplement pour obtenir le produit cartésien de deux tableaux ; cependant le deuxième tableau provient d'un appel récursif à la même fonction avec un tableau de moins ; donc a[0].cartesian(...a.slice(1))

Array.prototype.cartesian = function(...a){
  return a.length ? this.reduce((p,c) => (p.push(...a[0].cartesian(...a.slice(1)).map(e => a.length > 1 ? [c,...e] : [c,e])),p),[])
                  : this;
};

var arr = ['a', 'b', 'c'],
    brr = [1,2,3],
    crr = [[9],[8],[7]];
console.log(JSON.stringify(arr.cartesian(brr,crr)));

Answer 3

Dans mon cas particulier, l'approche "à l'ancienne" semblait être plus efficace que les méthodes basées sur des fonctionnalités plus modernes. Vous trouverez ci-dessous le code (y compris une petite comparaison avec d'autres solutions postées dans ce fil par @rsp et @sebnukem) au cas où il serait utile à quelqu'un d'autre.

L'idée est la suivante. Disons que nous construisons le produit externe de N les tableaux, a_1,...,a_N dont chacun a m_i composants. Le produit externe de ces tableaux a M=m_1*m_2*...*m_N et nous pouvons identifier chacun d'entre eux avec un N- vecteur de dimension dont les composantes sont des nombres entiers positifs et i -est strictement limité par le haut par m_i . Par exemple, le vecteur (0, 0, ..., 0) correspondrait à la combinaison particulière dans laquelle on prend le premier élément de chaque tableau, tandis 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, afin de construire tous les M la fonction ci-dessous construit consécutivement tous ces vecteurs et identifie pour chacun d'eux la combinaison correspondante des éléments des tableaux d'entrée.

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 j'obtiens les horaires suivants :

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

Answer 4

JavaScript moderne en quelques lignes seulement. Pas de bibliothèques externes ou de dépendances comme Lodash.

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

console.log(
  cartesian([1, 2], [10, 20], [100, 200, 300])
    .map(arr => JSON.stringify(arr))
    .join('\n')
);

Answer 5

Une autre réponse, encore plus simplifiée, de style 2021, utilisant uniquement les méthodes reduce, map et concat :

const cartesian = (...arr) => arr.reduce((a,c) => a.map(e => c.map(f => e.concat([f]))).reduce((a,c) => a.concat(c), []), [[]]);

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