wake-up-neo.com

Kartesisches Produkt aus mehreren Arrays in JavaScript

Wie würden Sie das kartesische Produkt mehrerer Arrays in JavaScript implementieren?

Als Beispiel,

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]...]
73
viebel

Hier ist eine funktionale Lösung für das Problem (ohne mutable variable!) Mit reduce und 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);
    }, [ [] ]);
};

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

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

84
viebel

Update 2017: 2-zeilige Antwort mit Vanilla JS

Alle Antworten hier sind zu kompliziert, die meisten von ihnen benötigen 20 Zeilen Code oder sogar mehr.

In diesem Beispiel werden nur zwei Zeilen von Vanilla JavaScript, kein lodash, Unterstrich oder andere Bibliotheken verwendet:

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, jedoch verbessert, um strikt dem Airbnb JavaScript Style Guide zu folgen - mit ESLint mit eslint-config-airbnb-base validiert:

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

Vielen Dank an ZuBB, dass Sie mich über Linter-Probleme 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 auf:

Syntax

Die Syntax, die ich hier verwendet habe, ist nichts Neues. Mein Beispiel verwendet den Spread-Operator und die Rest-Parameter - Funktionen von JavaScript, die in der 6. Ausgabe des ECMA-262-Standards definiert wurden, die im Juni 2015 veröffentlicht und viel früher entwickelt wurde 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 umzusetzen. In der Tat ist mein von Babel geschildertes Beispiel immer noch kürzer und einfacher als die meisten Beispiele hier, aber dies ist nicht der Fall Das ist wirklich wichtig, weil die Ausgabe der Transpilierung nicht etwas ist, das Sie verstehen oder pflegen müssen, es ist nur eine Tatsache, die ich interessant fand.

Fazit

Es ist nicht nötig, hunderte von Codezeilen zu schreiben, die schwer zu verwalten sind, und es ist nicht notwendig, ganze Bibliotheken für so einfache Dinge zu verwenden, wenn zwei Zeilen von Vanilla JavaScript die Arbeit leicht erledigen können. Wie Sie sehen, lohnt es sich wirklich, moderne Sprachfunktionen zu verwenden. Wenn Sie archaische Plattformen ohne native Unterstützung der modernen Funktionen unterstützen müssen, können Sie Babel oder andere Tools verwenden, um die neue Syntax auf die alte zu übertragen .

Codiere nicht wie 1995

JavaScript entwickelt sich aus einem bestimmten Grund. TC39 leistet erstaunliche Arbeit beim Design der Sprache, indem neue Funktionen hinzugefügt werden, und die Browseranbieter leisten erstaunliche Arbeit beim Implementieren dieser Funktionen.

Den aktuellen Status der systemeigenen Unterstützung einer bestimmten Funktion in den Browsern finden Sie unter:

Informationen zur Unterstützung in Knotenversionen finden Sie unter:

Verwenden Sie Babel, um die moderne Syntax auf Plattformen zu verwenden, die sie nicht nativ unterstützen.

64
rsp

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

es scheint, dass die Community dies für trivial hält oder einfach eine Referenzimplementierung findet. Nach kurzer Überprüfung konnte ich nicht oder vielleicht ist es einfach nur so, dass ich das Rad neu erfinden oder klassenzimmerartige Programmierprobleme lösen möchte :

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

die vollständige Referenzimplementierung ist relativ effizient ... :-D 

in Bezug auf die Effizienz: Sie könnten etwas davon gewinnen, wenn Sie das Wenn aus der Schleife nehmen und zwei separate Schleifen haben, da es technisch konstant ist und Sie mit der Verzweigungsvorhersage und all dem Durcheinander helfen würden

egal, genießen Sie -ck

27
ckozl

Hier ist eine unkomplizierte, 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]]
18
sebnukem

Die folgende effiziente Generatorfunktion gibt das kartesische Produkt aller angegebenen iterierbaren Elemente 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 iterable-Protokoll implementieren .

Nach der Spezifikation des n-ary-kartesischen Produkts ergibt es

  • [], wenn eine oder mehrere der angegebenen Iterables leer sind, z. [] oder ''
  • [[a]], wenn eine einzelne Iteration mit einem einzelnen Wert a angegeben ist.

Alle anderen Fälle werden wie erwartet behandelt, wie durch die folgenden Testfälle gezeigt:

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

16
le_m

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

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

function cartesianProduct(arrays) {
  var result = [],
      current = new Array(arrays.length);
  (function backtracking(index) {
    if(index == arrays.length) return result.Push(current.slice());
    for(var i=0; i<arrays[index].length; ++i) {
      current[index] = arrays[index][i];
      backtracking(index+1);
    }
  })(0);
  return result;
}
cartesianProduct([[1,2],[10,20],[100,200,300]]).forEach(function(item) {
  console.log('[' + item.join(', ') + ']');
});
div.as-console-wrapper { max-height: 100%; }

9
Oriol

Hier ist eine rekursive Methode, die eine ECMAScript 2015 generator-Funktion verwendet, damit Sie nicht alle Tupel auf einmal 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]))));

9
heenenee

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

7

Eine Kaffeeskriptversion mit lodash:

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

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 braucht ein einzelnes Array mit Arrays von gewünschten kartesischen Artikeln.

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

3
Nina Scholz

Einige Antworten in diesem Thema schlagen fehl, wenn eines der Eingabearrays ein Arrayelement enthält. Du prüfst das besser.

Wie auch immer, keine Notwendigkeit für Unterstreichung, lodash was auch immer. Ich glaube, dies sollte mit dem reinen JS ES6 so funktional sein, wie es nur geht.

Dieses Codeteil verwendet eine verkleinerte und eine verschachtelte Karte, um einfach das kartesische Produkt von zwei Arrays zu erhalten. Das zweite Array stammt jedoch von einem rekursiven Aufruf der gleichen 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))); 

3
Redu

In meinem speziellen Umfeld schien der "altmodische" Ansatz effizienter zu sein als die Methoden, die auf moderneren Funktionen basieren. Nachfolgend finden Sie den Code (einschließlich eines kleinen Vergleichs mit anderen Lösungen, die von @rsp und @sebnukem in diesem Thread veröffentlicht werden), falls sich dies auch für andere als nützlich erweisen sollte.

Die Idee folgt. Nehmen wir an, wir konstruieren das äußere Produkt von N-Arrays, von denen a_1,...,a_N jeweils m_i-Komponenten hat. Das äußere Produkt dieser Arrays hat M=m_1*m_2*...*m_N-Elemente, und wir können jedes von ihnen mit einem N-dimensionalen Vektor identifizieren, dessen Komponenten positive Ganzzahlen sind und die i- te Komponente von m_i von oben streng begrenzt ist. Zum Beispiel würde der Vektor (0, 0, ..., 0) der bestimmten Kombination entsprechen, innerhalb derer das erste Element aus jedem Array entnommen wird, während (m_1-1, m_2-1, ..., m_N-1) mit der Kombination identifiziert wird, bei der das letzte Element aus jedem Array entnommen wird. Um alle M-Kombinationen zu konstruieren, konstruiert die nachfolgende Funktion also alle diese Vektoren nacheinander und identifiziert für jeden von ihnen die entsprechende Kombination der Elemente der Eingabearrays.

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.2 bekomme ich folgende Timings:

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

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[][])
}
1
artnikpro

Dies ist mit functional-programming markiert. Schauen wir uns also die Liste monad an:

Eine Anwendung für diese monadische Liste ist die Darstellung nicht deterministischer Berechnungen. List kann Ergebnisse für alle Ausführungspfade enthalten in einem Algorithmus ...

Nun, das klingt wie ein perfekt fit für cartesian. JavaScript gibt uns Array und die monadische Bindungsfunktion ist Array.prototype.flatMap, also setzen wir sie ein -

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 loop oben kann t 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]))
1
user633183

Eine einfache Implementierung, die reduce von array verwendet:

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))), []);
1
Simple.Js

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')
);
1
Miles Elam

Ein nicht rekursiver Ansatz, der die Möglichkeit bietet, die Produkte zu filtern und zu ändern, bevor sie der Ergebnismenge hinzugefügt werden. Beachten Sie die Verwendung von .map anstelle von .forEach. In einigen Browsern läuft .map schneller.

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

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 ] ];
*/
0

Sie könnten reduceNAME _ das 2D-Array. Verwenden Sie flatMapNAME _ für das Akkumulator-Array, um acc.length x curr.length die Anzahl der Kombinationen in jeder Schleife abzurufen. [].concat(c, n) wird verwendet, weil ceine Zahl in der ersten Iteration und ein Array danach ist.

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

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

console.log(JSON.stringify(output))

(Dies basiert auf Nina Scholzs Antwort )

0
adiga

Mir ist aufgefallen, dass niemand eine Lösung gepostet 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?
0
Lezorte

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

Noch eine Implementierung. Nicht das 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;
}
0
flare256

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]))
0
Chris Vouga

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>

Just converted @dummersl's answer from CoffeScript to JavaScript. It just works.

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

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

 enter image description here


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

Für die Aufzeichnung

Hier geht es meiner Version davon. Ich habe es mit dem einfachsten JavaScript-Iterator "for ()" erstellt, damit es auf jeden 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.

0
LeandroP