Vraag Cartesisch product van meerdere arrays in JavaScript


Hoe zou u het Cartesiaanse product van meerdere arrays in JavaScript implementeren?

Als voorbeeld,

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

63
2017-09-06 15:59


oorsprong


antwoorden:


Hier is een functionele oplossing voor het probleem (zonder enige veranderlijke variabele!) gebruik makend van reduce en flatten, geleverd door 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"]] 

Opmerking: deze oplossing is geïnspireerd door http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/


80
2017-09-27 19:33



Update 2017: antwoord met 2 regels met vanille JS

Alle antwoorden zijn hier overdreven ingewikkeld, de meeste nemen 20 regels code of zelfs meer.

Dit voorbeeld gebruikt gewoon twee regels van vanille JavaScript, geen lodash, onderstrepingsteken of 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;

Bijwerken:

Dit is hetzelfde als hierboven, maar verbeterd om strikt te volgen Airbnb JavaScript-stijlgids - gevalideerd met behulp van ESLint met 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);

Speciale dank aan Zubb voor het me laten weten over linterproblemen met de originele code.

Voorbeeld

Dit is het exacte voorbeeld van uw vraag:

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

uitgang

Dit is de uitvoer van die opdracht:

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

demonstratie

Bekijk demo's op:

Syntaxis

De syntaxis die ik hier heb gebruikt, is niets nieuws. Mijn voorbeeld gebruikt de spreidoperator en de rustparameters - kenmerken van JavaScript gedefinieerd in de 6e editie van de ECMA-262-norm die in juni 2015 werd gepubliceerd en veel eerder is ontwikkeld, beter bekend als ES6 of ES2015. Zien:

Het maakt zo'n code zo eenvoudig dat het een zonde is om het niet te gebruiken. Voor oude platforms die dit niet native ondersteunen, kunt u altijd Babel of andere tools gebruiken om het naar een oudere syntaxis te transponeren - en in feite is mijn voorbeeld dat door Babel is overgenomen nog steeds korter en eenvoudiger dan de meeste voorbeelden hier, maar het doet dit niet er echt toe doet, omdat de output van transpilatie niet iets is dat je moet begrijpen of onderhouden, het is gewoon een feit dat ik interessant vond.

Conclusie

Het is niet nodig om honderd regels code te schrijven die moeilijk te onderhouden zijn en het is niet nodig om hele bibliotheken te gebruiken voor zoiets eenvoudigs, wanneer twee regels vanilla JavaScript de klus kunnen klaren. Zoals je kunt zien, loont het echt om moderne functies van de taal te gebruiken en in gevallen waar je archaïsche platforms moet ondersteunen zonder native ondersteuning van de moderne functies, kun je altijd Babel of andere tools gebruiken om de nieuwe syntaxis naar de oude over te brengen .

Codeer niet alsof het 1995 is

JavaScript evolueert en dit gebeurt met een reden. TC39 doet geweldig werk met het taalontwerp door nieuwe functies toe te voegen en de verkopers van browsers doen geweldig werk bij het implementeren van deze functies.

Zie: om de huidige status van native support van een bepaalde functie in de browsers te zien:

Zie de ondersteuning voor knooppuntversies:

Gebruik de Babel om moderne syntaxis te gebruiken op platforms die dit niet ondersteunen.


45
2018-03-27 18:23



Hier is een aangepaste versie van @ viebel's code in Javascript zonder een bibliotheek te gebruiken:

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

30
2018-03-26 10:31



het lijkt erop dat de gemeenschap denkt dat dit triviaal is en of gemakkelijk een referentie-implementatie te vinden, na een korte inspectie zou ik het niet kunnen of misschien is het gewoon dat ik graag het wiel opnieuw uitvind of klasachtige programmeerproblemen oplost, hoe dan ook je geluksdag :

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

volledige referentie-implementatie die relatief efficiënt is ... :-D

op efficiëntie: je zou er wat aan kunnen verdienen door de if uit de lus te nemen en twee aparte loops te hebben omdat het technisch constant is en je zou helpen met branchevoorspelling en al die rotzooi, maar dat punt is nogal een grap in javascript

wie dan ook, geniet van -ck


27
2017-09-06 17:16



Dit is een niet-fancy, eenvoudige recursieve oplossing:

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

14
2018-04-12 03:40



Met behulp van een typische backtracking met ES6-generators,

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

Hieronder is een vergelijkbare versie compatibel met oudere browsers.

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
2018-04-12 03:50



Dit is een recursieve manier waarop een ECMAScript 2015 wordt gebruikt generatorfunctie dus je hoeft niet alle tuples tegelijk te maken:

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


8
2017-08-24 00:22



Het volgende efficiënt generatorfunctie geeft het cartesiaanse product van alle gegeven terug iterables:

// Return cartesian product of given iterables:
function* cartesian(head, ...tail) {
  const remaining = tail.length > 0 ? cartesian(...tail) : [[]];
  for (let r of remaining) for (let h of head) yield [h, ...r];
}

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

Het accepteert arrays, strings, sets en alle andere objecten die het iterabel protocol.

Volgens de specificatie van de n-ary cartesisch product het levert op

  • [] als een of meer gegeven iterables leeg zijn, b.v. [] of ''
  • [[a]] als een enkele iterabele met een enkele waarde a is gegeven.

Alle andere gevallen worden behandeld zoals verwacht, zoals blijkt uit de volgende testgevallen:

// Return cartesian product of given iterables:
function* cartesian(head, ...tail) {
  const remaining = tail.length > 0 ? cartesian(...tail) : [[]];
  for (let r of remaining) 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]]


7
2018-05-16 21:49



Een versie met een coffeescript met lodash:

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

6
2018-03-02 23:38



Dit is een pure ES6-oplossing met pijl functies

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


6
2018-03-18 10:26



Een paar van de antwoorden onder dit onderwerp mislukken als een van de invoerarrays een arrayitem bevat. Dat kun je maar beter controleren.

Hoe dan ook geen noodzaak voor onderstreping, lodash dan ook. Ik geloof dat deze het met pure JS ES6 moet doen, zo functioneel als het maar kan.

Dit stuk code gebruikt een verkleinde en een geneste kaart, eenvoudigweg om het cartesiaanse product van twee matrices te krijgen, maar de tweede array komt van een recursieve aanroep naar dezelfde functie met één minder array; Vandaar.. 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
2017-10-02 16:10