Kartesisches Produkt mehrerer Arrays in JavaScript

110

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]
  ...
]
viebel
quelle
3
Dies wurde im Modul js-combinatorics implementiert: github.com/dankogai/js-combinatorics
Erel Segal-Halevi
Ich bin mit underscore.js einverstanden, aber ich bin nicht sicher, ob das Entfernen des Tags für die funktionale Programmierung @le_m
viebel
Fwiw, d3 d3.cross(a, b[, reducer])im Februar hinzugefügt . github.com/d3/d3-array#cross
Toph

Antworten:

105

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:

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;

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 :

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

Besonderer Dank geht an ZuBB, die mich über Linterprobleme mit dem Originalcode informiert haben.

Beispiel

Dies ist das genaue Beispiel aus Ihrer Frage:

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

Ausgabe

Dies ist die Ausgabe dieses Befehls:

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

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:

rsp
quelle
Hier ist eine Typoskript-Version mit einer geringfügigen Änderung, um die Art und Weise zu berücksichtigen, in der Typoskript die Array-Verbreitung ausführt. gist.github.com/ssippe/1f92625532eef28be6974f898efb23ef
Sam Sippe
1
@rsp vielen Dank für die wirklich gute Antwort. obwohl ich Sie bitten möchte, es ein wenig zu verbessern, um eine Warnung vor schattierten Variablen (2 lokale Variablen aund 2 lokale Variablen b) zu erhalten
ZuBB
7
"Codieren Sie nicht wie 1995" - Sie müssen nicht unangenehm sein, noch haben nicht alle aufgeholt.
Godwhacker
7
Dies ist in Ordnung, schlägt jedoch fehl, wenn es gefüttert ['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]].
Reduzieren Sie den
1
Da wir ...bereits verwenden, sollte nicht [].concat(...[array])einfach werden [...array]?
Lazar Ljubenović
88

Hier ist eine funktionale Lösung für das Problem (ohne veränderbare Variable !) Mit reduceund flatten, bereitgestellt von 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>

Anmerkung: Diese Lösung wurde von http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/ inspiriert.

viebel
quelle
Es gibt einen Tippfehler in dieser Antwort, es sollte kein ", wahr" geben (vielleicht hat sich lodash geändert, seit Sie diesen Beitrag verfasst haben?)
Chris Jefferson
@ChrisJefferson Der zweite Parameter flattenist, die Abflachung flach zu machen. Es ist hier obligatorisch!
Viebel
4
Entschuldigung, dies ist eine Inkompatibilität zwischen Lodash und Unterstrich. Sie haben die Flagge gewechselt.
Chris Jefferson
1
Also , wenn Abflachen Verwendung truemit Unterstrich und die Verwendung falsemit lodash flacher Abflachung zu gewährleisten.
Akseli Palén
Wie kann diese Funktion so geändert werden, dass sie ein Array von Arrays akzeptiert?
44

Hier ist eine modifizierte Version von @ viebels Code in einfachem Javascript, ohne eine Bibliothek zu verwenden:

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

Danny
quelle
2
Schlägt für kartesisches Produkt fehl ([[[1], [2], [3]], ['a', 'b'], [['gamma'], [['alpha']], ['zii', 'faa']]), da es ['gamma'] zu 'gamma' und [['alpha']] zu ['alpha']
abflacht
denn .concat(y)statt.concat([ y ])
Danke
@Danke, Sie können die Antwort direkt bearbeiten, anstatt sie zu kommentieren. Sie haben es jetzt einfach nicht nötig: P
Olivier Lalonde
28

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

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

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

ckozl
quelle
1
Vielen Dank an @ckoz für Ihre ausführliche Antwort. Warum würden Sie die reduceFunktion des Arrays nicht verwenden?
Viebel
1
@viebel warum willst du reduzieren verwenden? Zum einen hat Reduce eine sehr schlechte Unterstützung für ältere Browser (siehe: developer.mozilla.org/en-US/docs/JavaScript/Reference/… ), und auf jeden Fall sieht dieser verrückte Code aus dieser anderen Antwort für Sie tatsächlich lesbar aus ? es geht mich nichts an. Sicher, es ist kürzer, aber wenn dieser Code einmal minimiert ist, ist er ungefähr gleich lang, einfacher zu debuggen / zu optimieren. Zweitens sind alle "reduzierten" Lösungen auf das Gleiche beschränkt, außer dass sie eine Abschlusssuche haben (theoretisch langsamer). Es ist auch schwieriger zu entwerfen, so dass es unendliche Mengen handhabt ...
ckozl
5
Ich habe eine 2+ mal schnellere und (imo) sauberere Version erstellt: pastebin.com/YbhqZuf7 Sie erreicht den Geschwindigkeitsschub, wenn sie nicht verwendet result = result.concat(...)und nicht verwendet wird args.slice(1). Leider konnte ich keinen Weg finden, curr.slice()die Rekursion loszuwerden .
Pauan
2
@Pauan gute Arbeit, nette Reduzierung der Hot-Spots im Großen und Ganzen für in der Liga von 10% -50% Leistungssteigerung basierend auf dem, was ich sehe. Ich kann jedoch nicht über die "Sauberkeit" sprechen. Ich bin der Meinung, dass Ihre Version aufgrund der Verwendung von Variablen für den Abschlussbereich tatsächlich schwieriger zu befolgen ist. Im Allgemeinen ist es jedoch schwieriger, leistungsfähigeren Code zu befolgen. Ich habe die Originalversion aus Gründen der Lesbarkeit geschrieben. Ich wünschte, ich hätte mehr Zeit, damit ich Sie in einen Leistungsabfall verwickeln könnte.) Vielleicht später ...
verwickeln. ckozl
Dies ist wirklich eines dieser Probleme
James
26

Das Folgende effizient Generatorfunktion gibt das kartesische Produkt aller angegebenen Iterablen zurück :

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

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 Wert aangegeben wird.

Alle anderen Fälle werden wie erwartet behandelt, wie aus den folgenden Testfällen hervorgeht:

le_m
quelle
Haben Sie etwas dagegen zu erklären, was in diesem Fall passiert? Vielen Dank!
LeandroP
Vielen Dank, dass Sie uns ein wunderbares Beispiel für die Verwendung der Generatorfunktion + Schwanzrekursion + Doppelschichtschleifen beigebracht haben! Die Position der ersten for-Schleife im Code muss jedoch geändert werden, damit die Reihenfolge der Ausgabe-Sub-Arrays korrekt ist. Fester Code:function* cartesian(head, ...tail) { for (let h of head) { const remainder = tail.length > 0 ? cartesian(...tail) : [[]]; for (let r of remainder) yield [h, ...r] } }
ooo
@ooo Wenn Sie die Reihenfolge der kartesischen Produkttupel reproduzieren möchten, die im Kommentar von OP angegeben sind, ist Ihre Änderung korrekt. Die Reihenfolge der Tupel innerhalb des Produkts ist jedoch normalerweise nicht relevant, z. B. ist das Ergebnis mathematisch gesehen eine ungeordnete Menge. Ich habe diese Reihenfolge gewählt, weil sie viel weniger rekursive Aufrufe erfordert und daher etwas leistungsfähiger ist - ich habe jedoch keinen Benchmark durchgeführt.
le_m
Erratum: In meinem obigen Kommentar sollte "Schwanzrekursion" "Rekursion" sein (in diesem Fall kein Schwanzaufruf).
ooo
20

Hier ist eine ausgefallene, unkomplizierte rekursive Lösung:

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

sebnukem
quelle
2
Dies ist der effizienteste reine JS-Code unter diesem Thema. Es dauert ungefähr 600 ms, bis 3 x 100 Elementarrays fertig sind, um ein Array mit einer Länge von 1 MB zu erstellen.
Reduzieren Sie den
1
Funktioniert für kartesisches Produkt ([[[1], [2], [3]], ['a', 'b'], [['gamma'], [['alpha']], ['zii', 'faa']]); ohne die ursprünglichen Werte zu verflachen
Mzn
10

Hier ist eine rekursive Methode, die eine ECMAScript 2015- Generatorfunktion verwendet, sodass Sie nicht alle Tupel gleichzeitig erstellen müssen:

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

heenenee
quelle
Dies funktioniert nicht, wenn eines der Arrays Array-Elemente wiecartesian([[1],[2]],[10,20],[100,200,300])
Reduzieren Sie den
@Redu Answer wurde aktualisiert, um Array-Argumente zu unterstützen.
Heenenee
Ja, .concat()eingebauter Spread-Operator kann manchmal betrügerisch werden.
Reduzieren Sie den
10

Hier ist ein Einzeiler mit dem nativen ES2019 flatMap. Keine Bibliotheken erforderlich, nur ein moderner Browser (oder Transpiler):

data.reduce((a, b) => a.flatMap(x => b.map(y => [...x, y])), [[]]);

Es ist im Wesentlichen eine moderne Version von Viebels Antwort ohne Lodash.

Fred Kleuver
quelle
9

Verwenden eines typischen Backtracking mit ES6-Generatoren,

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

Unten finden Sie eine ähnliche Version, die mit älteren Browsern kompatibel ist.

Oriol
quelle
9

Dies ist eine reine ES6-Lösung mit Pfeilfunktionen

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

Christopher Moore
quelle
7

Eine Coffeescript-Version mit lodash:

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

Ein einzeiliger Ansatz zum besseren Lesen mit Einrückungen.

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

Es wird ein einzelnes Array mit Arrays gewünschter kartesischer Gegenstände benötigt.

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

Nina Scholz
quelle
Ich musste eine Guard-Anweisung hinzufügen, um den Fall korrekt zu behandeln, in dem das Array ein einzelnes Element enthält:if (arr.length === 1) return arr[0].map(el => [el]);
JacobEvelyn
5

Dies ist als funktionale Programmierung gekennzeichnet. Schauen wir uns also die Listenmonade an :

Eine Anwendung für diese monadische Liste repräsentiert die nichtdeterministische Berechnung. List kann Ergebnisse für alle Ausführungspfade in einem Algorithmus enthalten ...

Nun, das klingt nach einer perfekten Passform für cartesian. JavaScript gibt uns Arrayund die monadische Bindungsfunktion ist Array.prototype.flatMap, also lassen Sie uns sie verwenden -

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

Anstelle von loopoben tkann als Curry-Parameter hinzugefügt werden -

const makeCartesian = (t = []) => (a, ...more) =>
  a === undefined
    ? [ t ]
    : a .flatMap (x => makeCartesian ([ ...t, x ]) (...more))

const cartesian =
  makeCartesian ()

console .log (cartesian ([1,2], [10,20], [100,200,300]))

Danke dir
quelle
3

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

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

Reduzieren
quelle
3

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 NArrays, a_1,...,a_Nvon denen jedes m_iKomponenten enthält. Das äußere Produkt dieser Arrays hat M=m_1*m_2*...*m_NElemente, und wir können jedes von ihnen mit einem N-Dimensionsvektor identifizieren, dessen Komponenten positive ganze Zahlen sind und dessen i-te Komponente von oben streng durch begrenzt ist m_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

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

mit node v6.12.2bekomme ich folgende timings:

cartesianProduct: 427.378ms
cartesianProduct_rsp: 1710.829ms
cartesianProduct_sebnukem: 593.351ms
ewcz
quelle
3

Für diejenigen, die TypeScript benötigen (neu implementiert @ Dannys Antwort)

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

Nur zur Auswahl eine wirklich einfache Implementierung mit Arrays 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))), []);
Simple.Js
quelle
2

Modernes JavaScript in wenigen Zeilen. Keine externen Bibliotheken oder Abhängigkeiten wie Lodash.

function cartesian(...arrays) {
  return arrays.reduce((a, b) => a.flatMap(x => b.map(y => x.concat([y]))), [ [] ]);
}

console.log(
  cartesian([1, 2], [10, 20], [100, 200, 300])
    .map(arr => JSON.stringify(arr))
    .join('\n')
);

Miles Elam
quelle
2

Sie könnten reducedas 2D-Array. Verwenden Sie diese Option flatMapauf dem Akkumulator-Array, um die acc.length x curr.lengthAnzahl der Kombinationen in jeder Schleife abzurufen. [].concat(c, n)wird verwendet, weil ces sich bei der ersten Iteration um eine Zahl und danach um ein Array handelt.

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

(Dies basiert auf der Antwort von Nina Scholz )

adiga
quelle
1

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.

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;
    }
Wie auch immer
quelle
1

Eine einfache "geistige und visuell freundliche" Lösung.

Geben Sie hier die Bildbeschreibung ein


// 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']
));
null.zero.seven
quelle
1

Eine einfache, modifizierte Version von @ viebels Code in einfachem Javascript:

function cartesianProduct(...arrays) {
  return arrays.reduce((a, b) => {
    return [].concat(...a.map(x => {
      const next = Array.isArray(x) ? x : [x];
      return [].concat(b.map(y => next.concat(...[y])));
    }));
  });
}

const product = cartesianProduct([1, 2], [10, 20], [100, 200, 300]);

console.log(product);
/*
[ [ 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 ] ];
*/
Juan Gaitán
quelle
1

Eine besser lesbare Implementierung

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

Andrei
quelle
1
f=(a,b,c)=>a.flatMap(ai=>b.flatMap(bi=>c.map(ci=>[ai,bi,ci])))

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:

f(a,a,a)

aber verwendet:

f=(a,b,c)=>a.flatMap(a1=>a.flatMap(a2=>a.map(a3=>[a1,a2,a3])))
iAmOren
quelle
0

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:

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

Ausgabe:

Hello World!
Hello World?
Hello Planet!
Hello Planet?
Goodbye World!
Goodbye World?
Goodbye Planet!
Goodbye Planet?
Lezorte
quelle
0

Einfacher JS-Brute-Force-Ansatz, bei dem ein Array von Arrays als Eingabe verwendet wird.

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]
]);
Samuel Ventura
quelle
0

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))
<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>

Ich habe gerade die Antwort von @ dummersl von CoffeScript in JavaScript konvertiert . Es funktioniert einfach.

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) )
Guneysos
quelle
0

Noch eine Implementierung. Nicht die kürzeste oder schickste, aber schnell:

function cartesianProduct() {
    var arr = [].slice.call(arguments),
        intLength = arr.length,
        arrHelper = [1],
        arrToReturn = [];

    for (var i = arr.length - 1; i >= 0; i--) {
        arrHelper.unshift(arrHelper[0] * arr[i].length);
    }

    for (var i = 0, l = arrHelper[0]; i < l; i++) {
        arrToReturn.push([]);
        for (var j = 0; j < intLength; j++) {
            arrToReturn[i].push(arr[j][(i / arrHelper[j + 1] | 0) % arr[j].length]);
        }
    }

    return arrToReturn;
}
flare256
quelle
0

Keine Bibliotheken benötigt! :) :)

Benötigt Pfeilfunktionen und wahrscheinlich nicht so effizient. : /

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

const binaryCartesianProduct = (xs, ys) =>
    xs.map((xi) => ys.map((yi) => [xi, yi])).flat()

const cartesianProduct = (...xss) =>
    xss.reduce(binaryCartesianProduct, [[]]).map(flatten)
      
console.log(cartesianProduct([1,2,3], [1,2,3], [1,2,3]))

Chris Vouga
quelle
0

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.

function cartesian(arrays){
    var quant = 1, counters = [], retArr = [];

    // Counts total possibilities and build the counters Array;
    for(var i=0;i<arrays.length;i++){
        counters[i] = 0;
        quant *= arrays[i].length;
    }

    // iterate all possibilities
    for(var i=0,nRow;i<quant;i++){
        nRow = [];
        for(var j=0;j<counters.length;j++){
            if(counters[j] < arrays[j].length){
                nRow.push(arrays[j][counters[j]]);
            } else { // in case there is no such an element it restarts the current counter
                counters[j] = 0;
                nRow.push(arrays[j][counters[j]]);
            }
            counters[j]++;
        }
        retArr.push(nRow);
    }
    return retArr;
}

Freundliche Grüße.

LeandroP
quelle