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]
...
]
Réponse originale 2017 : réponse de 2 lignes avec vanilla JS : (voir les mises à jour ci-dessous)
Toutes les réponses ici sont trop compliqué la plupart d'entre elles nécessitent 20 lignes de code, voire plus.
Cet exemple n'utilise que deux lignes de vanilla JavaScript pas de lodash, underscore ou d'autres bibliothèques :
let f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesian = (a, b, ...c) => b ? cartesian(f(a, b), ...c) : a;C'est la même chose que ci-dessus mais amélioré pour suivre strictement le Guide de style JavaScript d'Airbnb - validée en utilisant ESLint con eslint-config-airbnb-base :
const f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesian = (a, b, ...c) => (b ? cartesian(f(a, b), ...c) : a);Remerciements particuliers à ZuBB pour m'avoir informé des problèmes de linter avec le code original.
Depuis que j'ai écrit cette réponse, nous avons obtenu des modules intégrés encore meilleurs, qui peuvent enfin nous permettre de réduire (sans jeu de mots) le code à une seule ligne !
const cartesian =
(...a) => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())));Remerciements particuliers à encreur pour avoir suggéré l'utilisation de reduce.
Remerciements particuliers à Bergi pour avoir suggéré l'utilisation de la flatMap nouvellement ajoutée.
Remerciements particuliers à ECMAScript 2019 pour avoir ajouté flat et flatMap au langage !
C'est l'exemple exact de votre question :
let output = cartesian([1,2],[10,20],[100,200,300]);Voici le résultat de cette commande :
[ [ 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 ] ]Voir les démos sur :
La syntaxe que j'ai utilisée ici n'est pas nouvelle. Mon exemple utilise l'opérateur d'étalement et les paramètres de repos - des caractéristiques de JavaScript définies dans la 6e édition de la norme ECMA-262 publiée le juin 2015 et développée bien avant, plus connue sous le nom de ES6 ou ES2015. Voir :
Les nouvelles méthodes de l'exemple de la mise à jour 2020 ont été ajoutées dans ES2019 :
Il rend ce genre de code si simple que c'est un péché de ne pas l'utiliser. Pour les anciennes plateformes qui ne le supportent pas nativement, vous pouvez toujours utiliser Babel ou d'autres outils pour le transposer dans une syntaxe plus ancienne - et en fait, mon exemple transposé par Babel est toujours plus court et plus simple que la plupart des exemples ici, mais cela n'a pas vraiment d'importance parce que le résultat de la transpilation n'est pas quelque chose que vous devez comprendre ou maintenir, c'est juste un fait que j'ai trouvé intéressant.
Il n'est pas nécessaire d'écrire des centaines de lignes de code difficiles à maintenir et il n'est pas nécessaire d'utiliser des bibliothèques entières pour une chose aussi simple, quand deux lignes de vanilla JavaScript peuvent facilement faire le travail. Comme vous pouvez le constater, l'utilisation des fonctionnalités modernes du langage est vraiment rentable et dans les cas où vous devez prendre en charge des plates-formes archaïques sans support natif des fonctionnalités modernes, vous pouvez toujours utiliser Babel , TypeScript ou d'autres outils pour transpiler la nouvelle syntaxe vers l'ancienne.
JavaScript évolue et il le fait pour une raison. Le CT39 fait un travail remarquable de conception du langage en ajoutant de nouvelles fonctionnalités et les fournisseurs de navigateurs font un travail remarquable de mise en œuvre de ces fonctionnalités.
Pour connaître l'état actuel de la prise en charge native d'une fonctionnalité donnée dans les navigateurs, voir :
Pour voir le support dans les versions de Node, voir :
Pour utiliser la syntaxe moderne sur des plateformes qui ne la prennent pas en charge de manière native, utilisez Babel ou TypeScript :
Voici une solution fonctionnelle au problème (sans aucune variable mutable !) en utilisant reduce et flatten fourni par underscore.js :
function cartesianProductOf() {
return _.reduce(arguments, function(a, b) {
return _.flatten(_.map(a, function(x) {
return _.map(b, function(y) {
return x.concat([y]);
});
}), true);
}, [ [] ]);
}
// [[1,3,"a"],[1,3,"b"],[1,4,"a"],[1,4,"b"],[2,3,"a"],[2,3,"b"],[2,4,"a"],[2,4,"b"]]
console.log(cartesianProductOf([1, 2], [3, 4], ['a']));
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore.js"></script>Remarques : Cette solution a été inspirée par http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/
Voici une version modifiée du code de @viebel en Javascript, sans utiliser de bibliothèque :
function cartesianProduct(arr) {
return arr.reduce(function(a,b){
return a.map(function(x){
return b.map(function(y){
return x.concat([y]);
})
}).reduce(function(a,b){ return a.concat(b) },[])
}, [[]])
}
var a = cartesianProduct([[1, 2,3], [4, 5,6], [7, 8], [9,10]]);
console.log(JSON.stringify(a));
L'efficacité suivante fonction de générateur renvoie le produit cartésien de tous les itérables :
// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
// Example:
console.log(...cartesian([1, 2], [10, 20], [100, 200, 300]));Il accepte les tableaux, les chaînes de caractères, les ensembles et tous les autres objets qui mettent en œuvre l'attribut protocole itérable .
Suite à la spécification de la produit cartésien n-aire on obtient
[] si un ou plusieurs itérables donnés sont vides, par exemple [] ou ''
[[a]] si une seule itérable contenant une seule valeur a est donné.Tous les autres cas sont traités comme prévu, comme le montrent les cas de test suivants :
// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
// Test cases:
console.log([...cartesian([])]); // []
console.log([...cartesian([1])]); // [[1]]
console.log([...cartesian([1, 2])]); // [[1], [2]]
console.log([...cartesian([1], [])]); // []
console.log([...cartesian([1, 2], [])]); // []
console.log([...cartesian([1], [2])]); // [[1, 2]]
console.log([...cartesian([1], [2], [3])]); // [[1, 2, 3]]
console.log([...cartesian([1, 2], [3, 4])]); // [[1, 3], [2, 3], [1, 4], [2, 4]]
console.log([...cartesian('')]); // []
console.log([...cartesian('ab', 'c')]); // [['a','c'], ['b', 'c']]
console.log([...cartesian([1, 2], 'ab')]); // [[1, 'a'], [2, 'a'], [1, 'b'], [2, 'b']]
console.log([...cartesian(new Set())]); // []
console.log([...cartesian(new Set([1]))]); // [[1]]
console.log([...cartesian(new Set([1, 1]))]); // [[1]]
Il semble que la communauté pense que cela est trivial et/ou qu'il est facile de trouver une implémentation de référence. Cependant, après une brève inspection, je n'ai pas pu en trouver une, ou peut-être est-ce simplement parce que j'aime réinventer la roue ou résoudre des problèmes de programmation dignes d'une salle de classe. Dans tous les cas, c'est votre jour de chance :
function cartProd(paramArray) {
function addTo(curr, args) {
var i, copy,
rest = args.slice(1),
last = !rest.length,
result = [];
for (i = 0; i < args[0].length; i++) {
copy = curr.slice();
copy.push(args[0][i]);
if (last) {
result.push(copy);
} else {
result = result.concat(addTo(copy, rest));
}
}
return result;
}
return addTo([], Array.prototype.slice.call(arguments));
}
>> console.log(cartProd([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]
]Une implémentation de référence complète qui est relativement efficace
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
