Kartesisches Produkt mehrerer Arrays in JavaScript

Question 1

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

Question 2

Hier ist eine funktionale Lösung des Problems (ohne veränderliche Variable!) verwenden reduce und flattenzur Verfügung gestellt 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 inspiriert von http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/

Question 3

Die folgenden effizient Generatorfunktion gibt das kartesische Produkt aller gegebenen zurück Iterables:

// 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 implementieren Iterierbares Protokoll.

Nach der Spezifikation der n-äres kartesisches Produkt es ergibt

[] wenn ein oder mehrere angegebene Iterables leer sind, z [] oder ''
[[a]] wenn ein einzelnes Iterable einen einzelnen Wert enthält a gegeben ist.

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

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

Question 4

Es scheint, dass die Community dies für trivial hält und/oder eine Referenzimplementierung leicht zu finden ist. Bei kurzem Hinsehen konnte ich jedoch keine finden, … entweder das, oder vielleicht liegt es einfach daran, dass ich gerne das Rad neu erfinde oder klassenzimmerähnliche Programmierprobleme löse. 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… 😁

Zur Effizienz: Sie könnten etwas gewinnen, indem Sie das if aus der Schleife nehmen und 2 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 irgendwie strittig.

Question 5

Hier ist eine nicht ausgefallene, einfache 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]
// ]