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 version coffeescript avec lodash :

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

Answer 2

Une approche sur une seule ligne, pour une meilleure lecture avec des indentations.

result = data.reduce(
    (a, b) => a.reduce(
        (r, v) => r.concat(b.map(w => [].concat(v, w))),
        []
    )
);

Il prend un tableau unique avec des tableaux d'éléments cartésiens souhaités.

var data = [[1, 2], [10, 20], [100, 200, 300]],
    result = data.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));

console.log(result.map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

programmation fonctionnelle

Cette question est étiquetée Programmation fonctionnelle alors jetons un coup d'oeil à la Monade de liste :

Une application de cette liste monadique est la représentation du calcul non déterministe. List peut contenir des résultats pour tous les chemins d'exécution dans un algorithme...

Eh bien, ça ressemble à un parfait pour cartesian . JavaScript nous donne Array et la fonction de liaison monadique est Array.prototype.flatMap alors mettons-les à profit

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

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

plus de récursion

D'autres implémentations récursives incluent -

const cartesian = (a, ...more) =>
  a == null
    ? [[]]
    : cartesian(...more).flatMap(c => a.map(v => [v,...c]))

for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))

.as-console-wrapper { min-height: 100%; top: 0; }

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

Notez l'ordre différent ci-dessus. Vous pouvez obtenir ordre lexicographique en inversant les deux boucles. Veillez à ne pas dupliquer le travail en appelant cartesian à l'intérieur de la boucle comme La réponse de Nick -

const bind = (x, f) => f(x)

const cartesian = (a, ...more) =>
  a == null
    ? [[]]
    : bind(cartesian(...more), r => a.flatMap(v => r.map(c => [v,...c])))

for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))

.as-console-wrapper { min-height: 100%; top: 0; }

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

générateurs

Une autre option consiste à utiliser des générateurs. Un générateur convient bien à la combinatoire, car l'espace des solutions peut devenir très vaste. Les générateurs offrent une évaluation paresseuse et peuvent donc être interrompus, repris ou annulés à tout moment.

function* cartesian(a, ...more) {
  if (a == null) return yield []
  for (const v of a)
    for (const c of cartesian(...more)) // ⚠️
      yield [v, ...c]
}

for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))

.as-console-wrapper { min-height: 100%; top: 0; }

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

Vous avez peut-être vu qu'on a appelé cartesian dans une boucle du générateur. Si vous pensez que cela peut être optimisé, c'est possible ! Ici, nous utilisons un générique tee fonction qui fait bifurquer tout itérateur n temps -

function* cartesian(a, ...more) {
  if (a == null) return yield []
  for (const t of tee(cartesian(...more), a.length)) // ✅
    for (const v of a)
      for (const c of t) // ✅
        yield [v, ...c]
}

Où tee est mis en œuvre comme -

function tee(g, n = 2) {
  const memo = []
  function* iter(i) {
    while (true) {
      if (i >= memo.length) {
        const w = g.next()
        if (w.done) return
        memo.push(w.value)
      }
      else yield memo[i++]
    }
  }
  return Array.from(Array(n), _ => iter(0))
}

Même dans les petits tests cartesian mis en œuvre avec tee est deux fois plus rapide.

Answer 4

Pour ceux qui ont besoin de TypeScript (réimplémentation de la réponse de @Danny)

/**
 * 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[][])
}

Answer 5

Vous pourriez reduce le tableau 2D. Utilisez flatMap sur le tableau de l'accumulateur pour obtenir acc.length x curr.length nombre de combinaisons dans chaque boucle. [].concat(c, n) est utilisé car c est un nombre lors de la première itération et un tableau par la suite.

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

const output = data.reduce((acc, curr) =>
  acc.flatMap(c => curr.map(n => [].concat(c, n)))
)

console.log(JSON.stringify(output))

(Ceci est basé sur La réponse de Nina Scholz )