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

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))

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

Juste converti @dummersl's réponse de CoffeScript à JavaScript. Ça marche 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) )

Answer 2

Pour mémoire

Voici ma version de la chose. Je l'ai fait en utilisant l'itérateur javascript le plus simple "for()", donc il est compatible dans tous les cas et a les meilleures performances.

function cartesian(arrays){
    var quant = 1, counters = [], retArr = [];

    // Counts total possibilities and build the counters Array;
    for(var i=0;i<arrays.length;i++){
        counters[i] = 0;
        quant *= arrays[i].length;
    }

    // iterate all possibilities
    for(var i=0,nRow;i<quant;i++){
        nRow = [];
        for(var j=0;j<counters.length;j++){
            if(counters[j] < arrays[j].length){
                nRow.push(arrays[j][counters[j]]);
            } else { // in case there is no such an element it restarts the current counter
                counters[j] = 0;
                nRow.push(arrays[j][counters[j]]);
            }
            counters[j]++;
        }
        retArr.push(nRow);
    }
    return retArr;
}

Meilleures salutations.

Answer 3

Version 2021 du grand livre de David Tang réponse
Inspiré également par le livre de Neil Mountford réponse

• rapide (plus rapide que la réponse acceptée de 95%)

• fonctionne avec tous les types de données

  const getAllCombinations = (arraysToCombine) => { const divisors = []; let combinationsCount = 1; for (let i = arraysToCombine.length - 1; i >= 0; i--) { divisors[i] = divisors[i + 1] ? divisors[i + 1] arraysToCombine[i + 1].length : 1; combinationsCount = (arraysToCombine[i].length || 1); }

  const getCombination = (n, arrays, divisors) => arrays.reduce((acc, arr, i) => { acc.push(arr[Math.floor(n / divisors[i]) % arr.length]); return acc; }, []);

  const combinations = []; for (let i = 0; i < combinationsCount; i++) { combinations.push(getCombination(i, arraysToCombine, divisors)); } return combinations; };

  console.log(getAllCombinations([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']]));

Repères : https://jsbench.me/gdkmxhm36d/1

Answer 4

Une approche de force brute en JS 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]
]);

Answer 5

Le moyen le plus simple d'y parvenir est d'utiliser la méthode ES6. Tout le monde doit avoir compris comment fonctionne un diagramme de Venn. Donc, de la même manière, ES6 nous fournit un moyen d'effectuer toutes les opérations sur n'importe quel type de structure de données.

Prenons l'exemple suivant

var arr1 = [1,2,2,3,5] var arr2 = [2,3,5,6,7]

arr1.filter(x => arr2.includes(x))

Résultat => [2,2,3,5]

Nous pouvons voir que "2" a été répété dans le résultat, ce qui peut être évité en utilisant la classe Set fournie sur l'un des tableaux. comme mentionné dans les réponses ci-dessus

[... new Set(arr1)].filter(x => arr2.includes(x))

Résultat => [2,3,5]