Prodotto cartesiano di più array in JavaScript

Come implementeresti il ​​prodotto cartesiano di più array in JavaScript?

Come esempio,

cartesian([1,2],[10,20],[100,200,300]) //should be // [[1,10,100],[1,10,200],[1,10,300],[2,10,100],[2,10,200]...] 

Ecco una soluzione funzionale al problema (senza alcuna variabile mutevole !) Usando reduce e flatten , fornito da 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); }, [ [] ]); }; cartesianProductOf([1, 2], [3, 4], ['a', 'b']); // [[1,3,"a"],[1,3,"b"],[1,4,"a"],[1,4,"b"],[2,3,"a"],[2,3,"b"],[2,4,"a"],[2,4,"b"]] 

Nota: questa soluzione è stata ispirata da http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/

Aggiornamento 2017: risposta in 2 righe con vanilla JS

Tutte le risposte qui sono eccessivamente complicate , la maggior parte prende 20 righe di codice o anche di più.

Questo esempio utilizza solo due righe di JavaScript vaniglia , no lodash, underscore o altre librerie:

 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; 

Aggiornare:

È lo stesso di sopra, ma è stato migliorato per seguire rigorosamente la Guida allo stile JavaScript di Airbnb – convalidata utilizzando 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); 

Un ringraziamento speciale a ZuBB per avermi fatto conoscere problemi di linter con il codice originale.

Esempio

Questo è l’esatto esempio della tua domanda:

 let output = cartesian([1,2],[10,20],[100,200,300]); 

Produzione

Questo è l’output di quel comando:

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

dimostrazione

Guarda le demo su:

  • JS Bin with Babel (per vecchi browser)
  • JS Bin senza Babel (per browser moderni)

Sintassi

La syntax che ho usato qui non è nulla di nuovo. Il mio esempio utilizza l’operatore di spread e i parametri di resto – le funzionalità di JavaScript definite nella sesta edizione dello standard ECMA-262 pubblicate a giugno 2015 e sviluppate molto prima, meglio conosciute come ES6 o ES2015. Vedere:

Rende il codice così semplice che è un peccato non usarlo. Per le vecchie piattaforms che non lo supportano in modo nativo puoi sempre usare Babel o altri strumenti per traspolarlo in una syntax più vecchia – e infatti il ​​mio esempio transpiled da Babel è ancora più breve e più semplice della maggior parte degli esempi qui, ma non davvero importante perché l’output di transpilation non è qualcosa che devi capire o mantenere, è solo un fatto che ho trovato interessante.

Conclusione

Non è necessario scrivere centinaia di righe di codice che è difficile da mantenere e non è necessario utilizzare intere librerie per una cosa così semplice, quando due linee di vanilla JavaScript possono facilmente portare a termine il lavoro. Come puoi vedere, vale la pena utilizzare le funzionalità moderne della lingua e nei casi in cui devi supportare piattaforms arcaiche senza supporto nativo delle funzionalità moderne puoi sempre usare Babel o altri strumenti per traspolare la nuova syntax in quella vecchia .

Non scrivere come nel 1995

JavaScript si evolve e lo fa per una ragione. TC39 svolge un ottimo lavoro nella progettazione della lingua con l’aggiunta di nuove funzionalità ei produttori di browser svolgono un lavoro straordinario nell’implementare queste funzionalità.

Per vedere lo stato attuale del supporto nativo di una determinata funzione nei browser, vedere:

Per vedere il supporto nelle versioni dei nodes, vedere:

Per usare la syntax moderna su piattaforms che non la supportano in modo nativo, usa Babel:

Ecco una versione modificata del codice di @ viebel in semplice Javascript, senza utilizzare alcuna libreria:

 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(a); 

sembra che la comunità pensi che sia banale e facile trovare un’implementazione di riferimento, a breve ispezione non potevo o forse è solo che mi piace reinventare la ruota o risolvere problemi di programmazione simili a una class in ogni modo il suo fortunato giorno :

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

implementazione di riferimento completa che è relativamente efficiente … MrGreen

sull’efficienza: potresti ottenerne un po ‘prendendo il se fuori dal ciclo e avendo 2 loop separati poiché è tecnicamente costante e starai aiutando con la previsione del ramo e tutto quel casino, ma quel punto è un po’ discutibile in javascript

chi vuoi, divertiti -ck

Ecco una soluzione ricorsiva semplice e non sofisticata:

 function cartesianProduct(a) { // a = array of array var i, j, l, m, a1, o = []; if (!a || a.length == 0) return a; a1 = a.splice(0, 1)[0]; // the first array of a a = cartesianProduct(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; } console.log(cartesianProduct([[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]] 

Ecco un modo ricorsivo che utilizza una funzione generatore ECMAScript 2015 in modo da non dover creare tutte le tuple contemporaneamente:

 function* cartesian() { let arrays = arguments; function* doCartesian(i, prod) { if (i == arrays.length) { yield prod; } else { for (let j = 0; j < arrays[i].length; j++) { yield* doCartesian(i + 1, prod.concat([arrays[i][j]])); } } } yield* doCartesian(0, []); } console.log(JSON.stringify(Array.from(cartesian([1,2],[10,20],[100,200,300])))); console.log(JSON.stringify(Array.from(cartesian([[1],[2]],[10,20],[100,200,300])))); 

Utilizzando un tipico backtracking con i generatori ES6,

 function cartesianProduct(...arrays) { let current = new Array(arrays.length); return (function* backtracking(index) { if(index == arrays.length) yield current.slice(); else for(let num of arrays[index]) { current[index] = num; yield* backtracking(index+1); } })(0); } for (let item of cartesianProduct([1,2],[10,20],[100,200,300])) { console.log('[' + item.join(', ') + ']'); } 
 div.as-console-wrapper { max-height: 100%; } 

La seguente efficiente funzione di generatore restituisce il prodotto cartesiano di tutti gli iterabili forniti:

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

Una versione coffeescript con lodash:

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

Questa è una pura soluzione ES6 che utilizza le funzioni di freccia

 function cartesianProduct(arr) { return arr.reduce((a, b) => a.map(x => b.map(y => x.concat(y))) .reduce((a, b) => a.concat(b), []), [[]]); } var arr = [[1, 2], [10, 20], [100, 200, 300]]; console.log(JSON.stringify(cartesianProduct(arr))); 

Alcune delle risposte a questo argomento non riescono quando uno qualsiasi degli array di input contiene un elemento dell’array. Farai meglio a controllarlo.

Comunque non c’è bisogno di sottolineare, lodash qualunque. Credo che questo dovrebbe farlo con puro JS ES6, tanto funzionale quanto diventa.

Questo pezzo di codice usa una mappa ridotta e una mappa nidificata, semplicemente per ottenere il prodotto cartesiano di due array, tuttavia il secondo array deriva da una chiamata ricorsiva alla stessa funzione con un array in meno; quindi .. 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))); 

Nel mio ambiente particolare, l’approccio “vecchio stile” sembrava essere più efficiente dei metodi basati su caratteristiche più moderne. Di seguito è riportato il codice (incluso un piccolo confronto con altre soluzioni pubblicate in questa discussione da @rsp e @sebnukem) qualora si riveli utile anche a qualcun altro.

L’idea sta seguendo. Diciamo che stiamo costruendo il prodotto esterno degli array N , a_1,...,a_N ognuno dei quali ha componenti m_i . Il prodotto esterno di questi array ha elementi M=m_1*m_2*...*m_N e possiamo identificare ciascuno di essi con un vettore N- dimensionale i cui componenti sono numeri interi positivi e il componente i -th è strettamente limitato dall’alto m_i . Ad esempio, il vettore (0, 0, ..., 0) corrisponderebbe alla particolare combinazione all’interno della quale si prende il primo elemento da ogni matrice, mentre (m_1-1, m_2-1, ..., m_N-1) è identificato con la combinazione in cui si prende l’ultimo elemento da ogni matrice. Quindi, al fine di build tutte le combinazioni M , la funzione seguente costruisce consecutivamente tutti questi vettori e per ognuno di essi identifica la corrispondente combinazione degli elementi degli array di input.

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

con il node v6.12.2 , ottengo i seguenti tempi:

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

Un approccio non ricorsivo che aggiunge la possibilità di filtrare e modificare i prodotti prima di aggiungerli effettivamente al set di risultati. Notare l’uso di .map anziché di .forEach. In alcuni browser, .map viene eseguito più velocemente.

 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; } 

Giusto per una scelta, un’implementazione semplice e semplice con l’uso di array 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))), []); 

Ho notato che nessuno ha pubblicato una soluzione che consente di passare una funzione per elaborare ogni combinazione, quindi ecco la mia soluzione:

 const _ = require('lodash') function combinations(arr, f, xArr = []) { return arr.length>1 ? _.flatMap(arr[0], x => combinations(arr.slice(1), f, xArr.concat(x))) : arr[0].map(x => f(...xArr.concat(x))) } // use case const greetings = ["Hello", "Goodbye"] const places = ["World", "Planet"] const punctuationMarks = ["!", "?"] combinations([greetings,places,punctuationMarks], (greeting, place, punctuationMark) => `${greeting} ${place}${punctuationMark}`) .forEach(row => console.log(row)) 

Produzione:

 Hello World! Hello World? Hello Planet! Hello Planet? Goodbye World! Goodbye World? Goodbye Planet! Goodbye Planet? 

Semplice approccio a forza bruta di JS che prende come input una serie di matrici.

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

Una semplice soluzione “mente e visivamente amichevole”.

inserisci la descrizione dell'immagine qui


 // 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'] )); 
 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)) 
  

Un approccio a linea singola, per una migliore lettura con indentazioni.

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

Richiede un singolo array con array di elementi cartesiani ricercati.

 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; }