Wie würden Sie das kartesische Produkt mehrerer Arrays in JavaScript implementieren?
Als Beispiel,
cartesian([1, 2], [10, 20], [100, 200, 300])
sollte zurückkehren
[
[1, 10, 100],
[1, 10, 200],
[1, 10, 300],
[2, 10, 100],
[2, 10, 200]
...
]
d3.cross(a, b[, reducer])
im Februar hinzugefügt . github.com/d3/d3-array#crossAntworten:
Update 2017: 2-zeilige Antwort mit Vanilla JS
Alle Antworten hier sind zu kompliziert . Die meisten von ihnen benötigen 20 Codezeilen oder sogar mehr.
In diesem Beispiel werden nur zwei Zeilen Vanille-JavaScript verwendet , kein Lodash, Unterstrich oder andere Bibliotheken:
Aktualisieren:
Dies ist das gleiche wie oben, wurde jedoch verbessert, um den Airbnb JavaScript Style Guide genau zu befolgen - validiert mit ESLint mit eslint-config-airbnb-base :
Besonderer Dank geht an ZuBB, die mich über Linterprobleme mit dem Originalcode informiert haben.
Beispiel
Dies ist das genaue Beispiel aus Ihrer Frage:
Ausgabe
Dies ist die Ausgabe dieses Befehls:
Demo
Siehe Demos zu:
Syntax
Die Syntax, die ich hier verwendet habe, ist nichts Neues. In meinem Beispiel werden der Spread-Operator und die Restparameter verwendet - Funktionen von JavaScript, die in der 6. Ausgabe des im Juni 2015 veröffentlichten und viel früher entwickelten ECMA-262-Standards definiert wurden, besser bekannt als ES6 oder ES2015. Sehen:
Es macht Code wie diesen so einfach, dass es eine Sünde ist, ihn nicht zu benutzen. Für alte Plattformen, die es nicht nativ unterstützen, können Sie immer Babel oder andere Tools verwenden, um es auf ältere Syntax zu transpilieren - und tatsächlich ist mein von Babel transpiliertes Beispiel immer noch kürzer und einfacher als die meisten Beispiele hier, aber es ist nicht so wirklich wichtig, weil die Ausgabe der Transpilation nicht etwas ist, das Sie verstehen oder aufrechterhalten müssen, sondern nur eine Tatsache, die ich interessant fand.
Fazit
Es ist nicht erforderlich, Hunderte von Codezeilen zu schreiben, die schwer zu warten sind, und es ist nicht erforderlich, ganze Bibliotheken für eine so einfache Sache zu verwenden, wenn zwei Zeilen Vanille-JavaScript die Aufgabe problemlos erledigen können. Wie Sie sehen, lohnt es sich wirklich, moderne Funktionen der Sprache zu verwenden. In Fällen, in denen Sie archaische Plattformen ohne native Unterstützung der modernen Funktionen unterstützen müssen, können Sie immer Babel oder andere Tools verwenden, um die neue Syntax auf die alte zu übertragen .
Codieren Sie nicht wie 1995
JavaScript entwickelt sich aus einem bestimmten Grund weiter. TC39 leistet hervorragende Arbeit im Sprachdesign, indem es neue Funktionen hinzufügt, und die Browser-Anbieter leisten hervorragende Arbeit bei der Implementierung dieser Funktionen.
Informationen zum aktuellen Status der nativen Unterstützung einer bestimmten Funktion in den Browsern finden Sie unter:
Informationen zur Unterstützung in Node-Versionen finden Sie unter:
Verwenden Sie Babel, um die moderne Syntax auf Plattformen zu verwenden, die sie nicht nativ unterstützen:
quelle
a
und 2 lokale Variablenb
) zu erhalten['a', 'b'], [1,2], [[9], [10]]
wird,[ [ 'a', 1, 9 ], [ 'a', 1, 10 ], [ 'a', 2, 9 ], [ 'a', 2, 10 ], [ 'b', 1, 9 ], [ 'b', 1, 10 ], [ 'b', 2, 9 ], [ 'b', 2, 10 ] ]
was zu einem Ergebnis führt. Ich meine, ich werde die Art der Gegenstände von nicht behalten[[9], [10]]
....
bereits verwenden, sollte nicht[].concat(...[array])
einfach werden[...array]
?Hier ist eine funktionale Lösung für das Problem (ohne veränderbare Variable !) Mit
reduce
undflatten
, bereitgestellt vonunderscore.js
:Anmerkung: Diese Lösung wurde von http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/ inspiriert.
quelle
flatten
ist, die Abflachung flach zu machen. Es ist hier obligatorisch!true
mit Unterstrich und die Verwendungfalse
mit lodash flacher Abflachung zu gewährleisten.Hier ist eine modifizierte Version von @ viebels Code in einfachem Javascript, ohne eine Bibliothek zu verwenden:
quelle
.concat(y)
statt.concat([ y ])
Es scheint, dass die Community dies für trivial und / oder einfach hält, um eine Referenzimplementierung zu finden. Nach einer kurzen Inspektion konnte ich es nicht oder vielleicht mag ich es einfach, das Rad neu zu erfinden oder klassenzimmerähnliche Programmierprobleme zu lösen, so oder so ist es Ihr Glückstag ::
vollständige Referenzimplementierung, die relativ effizient ist ... :-D
Effizienz: Sie könnten einige davon gewinnen, indem Sie das if aus der Schleife nehmen und zwei separate Schleifen haben, da es technisch konstant ist und Sie bei der Verzweigungsvorhersage und all dem Durcheinander helfen würden, aber dieser Punkt ist in Javascript ein bisschen umstritten
Wie auch immer, genieße -ck
quelle
reduce
Funktion des Arrays nicht verwenden?result = result.concat(...)
und nicht verwendet wirdargs.slice(1)
. Leider konnte ich keinen Weg finden,curr.slice()
die Rekursion loszuwerden .Das Folgende effizient Generatorfunktion gibt das kartesische Produkt aller angegebenen Iterablen zurück :
Es akzeptiert Arrays, Strings, Sets und alle anderen Objekte, die das iterierbare Protokoll implementieren .
Nach der Spezifikation des n-ary kartesischen Produkts ergibt es
[]
wenn eine oder mehrere gegebene Iterables leer sind, z. B.[]
oder''
[[a]]
wenn eine einzelne Iterable mit einem einzelnen Werta
angegeben wird.Alle anderen Fälle werden wie erwartet behandelt, wie aus den folgenden Testfällen hervorgeht:
Code-Snippet anzeigen
quelle
function* cartesian(head, ...tail) { for (let h of head) { const remainder = tail.length > 0 ? cartesian(...tail) : [[]]; for (let r of remainder) yield [h, ...r] } }
Hier ist eine ausgefallene, unkomplizierte rekursive Lösung:
quelle
Hier ist eine rekursive Methode, die eine ECMAScript 2015- Generatorfunktion verwendet, sodass Sie nicht alle Tupel gleichzeitig erstellen müssen:
quelle
cartesian([[1],[2]],[10,20],[100,200,300])
.concat()
eingebauter Spread-Operator kann manchmal betrügerisch werden.Hier ist ein Einzeiler mit dem nativen ES2019
flatMap
. Keine Bibliotheken erforderlich, nur ein moderner Browser (oder Transpiler):Es ist im Wesentlichen eine moderne Version von Viebels Antwort ohne Lodash.
quelle
Verwenden eines typischen Backtracking mit ES6-Generatoren,
Unten finden Sie eine ähnliche Version, die mit älteren Browsern kompatibel ist.
Code-Snippet anzeigen
quelle
Dies ist eine reine ES6-Lösung mit Pfeilfunktionen
quelle
Eine Coffeescript-Version mit lodash:
quelle
Ein einzeiliger Ansatz zum besseren Lesen mit Einrückungen.
Es wird ein einzelnes Array mit Arrays gewünschter kartesischer Gegenstände benötigt.
quelle
if (arr.length === 1) return arr[0].map(el => [el]);
Dies ist als funktionale Programmierung gekennzeichnet. Schauen wir uns also die Listenmonade an :
Nun, das klingt nach einer perfekten Passform für
cartesian
. JavaScript gibt unsArray
und die monadische Bindungsfunktion istArray.prototype.flatMap
, also lassen Sie uns sie verwenden -Anstelle von
loop
obent
kann als Curry-Parameter hinzugefügt werden -quelle
Einige der Antworten unter diesem Thema schlagen fehl, wenn eines der Eingabearrays ein Arrayelement enthält. Überprüfen Sie das besser.
Wie auch immer, es ist kein Unterstrich nötig. Ich glaube, dies sollte mit reinem JS ES6 geschehen, so funktional wie es nur geht.
Dieser Code verwendet eine verkleinerte und eine verschachtelte Karte, um einfach das kartesische Produkt zweier Arrays zu erhalten. Das zweite Array stammt jedoch aus einem rekursiven Aufruf derselben Funktion mit einem Array weniger. daher..
a[0].cartesian(...a.slice(1))
quelle
In meiner besonderen Umgebung schien der "altmodische" Ansatz effizienter zu sein als die Methoden, die auf moderneren Merkmalen basieren. Unten finden Sie den Code (einschließlich eines kleinen Vergleichs mit anderen Lösungen, die in diesem Thread von @rsp und @sebnukem veröffentlicht wurden), falls er sich auch für andere als nützlich erweisen sollte.
Die Idee folgt. Nehmen wir an, wir konstruieren das äußere Produkt von
N
Arrays,a_1,...,a_N
von denen jedesm_i
Komponenten enthält. Das äußere Produkt dieser Arrays hatM=m_1*m_2*...*m_N
Elemente, und wir können jedes von ihnen mit einemN-
Dimensionsvektor identifizieren, dessen Komponenten positive ganze Zahlen sind und desseni
-te Komponente von oben streng durch begrenzt istm_i
. Beispielsweise konstruieren die Vektorkombinationen , die folgende Funktion, nacheinander alle derartigen Vektoren und identifizieren für jeden von ihnen die entsprechende Kombination der Elemente der Eingabearrays.(0, 0, ..., 0)
würde der bestimmten Kombination entsprechen, innerhalb derer man das erste Element von jedem Array nimmt, während er(m_1-1, m_2-1, ..., m_N-1)
mit der Kombination identifiziert wird, bei der man das letzte Element von jedem Array nimmt. Also um alles zu konstruierenM
mit
node v6.12.2
bekomme ich folgende timings:quelle
Für diejenigen, die TypeScript benötigen (neu implementiert @ Dannys Antwort)
quelle
Nur zur Auswahl eine wirklich einfache Implementierung mit Arrays
reduce
:quelle
Modernes JavaScript in wenigen Zeilen. Keine externen Bibliotheken oder Abhängigkeiten wie Lodash.
quelle
Sie könnten
reduce
das 2D-Array. Verwenden Sie diese OptionflatMap
auf dem Akkumulator-Array, um dieacc.length x curr.length
Anzahl der Kombinationen in jeder Schleife abzurufen.[].concat(c, n)
wird verwendet, weilc
es sich bei der ersten Iteration um eine Zahl und danach um ein Array handelt.(Dies basiert auf der Antwort von Nina Scholz )
quelle
Ein nicht rekursiver Ansatz, der die Möglichkeit bietet, die Produkte zu filtern und zu ändern, bevor sie tatsächlich zur Ergebnismenge hinzugefügt werden. Beachten Sie die Verwendung von .map anstelle von .forEach. In einigen Browsern wird .map schneller ausgeführt.
quelle
Eine einfache "geistige und visuell freundliche" Lösung.
quelle
Eine einfache, modifizierte Version von @ viebels Code in einfachem Javascript:
quelle
Eine besser lesbare Implementierung
quelle
Dies ist für 3 Arrays.
Einige Antworten gaben Platz für eine beliebige Anzahl von Arrays.
Dies kann sich leicht zusammenziehen oder auf weniger oder mehr Arrays erweitern.
Ich brauchte Kombinationen eines Satzes mit Wiederholungen, also hätte ich verwenden können:
aber verwendet:
quelle
Mir ist aufgefallen, dass niemand eine Lösung veröffentlicht hat, mit der eine Funktion zur Verarbeitung jeder Kombination übergeben werden kann. Hier ist meine Lösung:
Ausgabe:
quelle
Einfacher JS-Brute-Force-Ansatz, bei dem ein Array von Arrays als Eingabe verwendet wird.
quelle
Ich habe gerade die Antwort von @ dummersl von CoffeScript in JavaScript konvertiert . Es funktioniert einfach.
quelle
Noch eine Implementierung. Nicht die kürzeste oder schickste, aber schnell:
quelle
Keine Bibliotheken benötigt! :) :)
Benötigt Pfeilfunktionen und wahrscheinlich nicht so effizient. : /
quelle
Für die Aufzeichnung
Hier geht es meine Version davon. Ich habe es mit dem einfachsten Javascript-Iterator "for ()" gemacht, damit es in jedem Fall kompatibel ist und die beste Leistung bietet.
Freundliche Grüße.
quelle