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

Une mise en œuvre plus lisible

function productOfTwo(one, two) {
  return one.flatMap(x => two.map(y => [].concat(x, y)));
}

function product(head = [], ...tail) {
  if (tail.length === 0) return head;
  return productOfTwo(head, product(...tail));
}

const test = product(
  [1, 2, 3],
  ['a', 'b']
);

console.log(JSON.stringify(test));

Answer 2

Pour ceux qui se contentent d'une solution ramda :

import { xprod, flatten } from 'ramda';

const cartessian = (...xs) => xs.reduce(xprod).map(flatten)

Ou la même chose sans dépendances et deux blocs lego gratuits ( xprod et flatten ) :

const flatten = xs => xs.flat();

const xprod = (xs, ys) => xs.flatMap(x => ys.map(y => [x, y]));

const cartessian = (...xs) => xs.reduce(xprod).map(flatten);

Answer 3

Une approche non récursive qui ajoute la possibilité de filtrer et de modifier les produits avant de les ajouter effectivement à l'ensemble des résultats.

Remarque : l'utilisation de .map plutôt que .forEach . Dans certains navigateurs, .map fonctionne plus rapidement.

function crossproduct(arrays, rowtest, rowaction) {
  // Calculate the number of elements needed in the result
  var result_elems = 1, row_size = arrays.length;
  arrays.map(function(array) {
    result_elems *= array.length;
  });
  var temp = new Array(result_elems), result = [];

  // Go through each array and add the appropriate
  // element to each element of the temp
  var scale_factor = result_elems;
  arrays.map(function(array) {
    var set_elems = array.length;
    scale_factor /= set_elems;
    for (var i = result_elems - 1; i >= 0; i--) {
      temp[i] = (temp[i] ? temp[i] : []);
      var pos = i / scale_factor % set_elems;
      // deal with floating point results for indexes,
      // this took a little experimenting
      if (pos < 1 || pos % 1 <= .5) {
        pos = Math.floor(pos);
      } else {
        pos = Math.min(array.length - 1, Math.ceil(pos));
      }
      temp[i].push(array[pos]);
      if (temp[i].length === row_size) {
        var pass = (rowtest ? rowtest(temp[i]) : true);
        if (pass) {
          if (rowaction) {
            result.push(rowaction(temp[i]));
          } else {
            result.push(temp[i]);
          }
        }
      }
    }
  });
  return result;
}

Answer 4

Pour faire un choix, une mise en œuvre très simple utilisant des tableaux. 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))), []);

Answer 5

Une solution simple et conviviale pour l'esprit et l'image.

---

// t = [i, length]

const moveThreadForwardAt = (t, tCursor) => {
  if (tCursor < 0)
    return true; // reached end of first array

  const newIndex = (t[tCursor][0] + 1) % t[tCursor][1];
  t[tCursor][0] = newIndex;

  if (newIndex == 0)
    return moveThreadForwardAt(t, tCursor - 1);

  return false;
}

const cartesianMult = (...args) => {
  let result = [];
  const t = Array.from(Array(args.length)).map((x, i) => [0, args[i].length]);
  let reachedEndOfFirstArray = false;

  while (false == reachedEndOfFirstArray) {
    result.push(t.map((v, i) => args[i][v[0]]));

    reachedEndOfFirstArray = moveThreadForwardAt(t, args.length - 1);
  }

  return result;
}

// cartesianMult(
//   ['a1', 'b1', 'c1'],
//   ['a2', 'b2'],
//   ['a3', 'b3', 'c3'],
//   ['a4', 'b4']
// );

console.log(cartesianMult(
  ['a1'],
  ['a2', 'b2'],
  ['a3', 'b3']
));