JavaScript – Generieren von Kombinationen aus n Arrays mit m Elementen [duplicate]

Ich habe Probleme beim Erstellen von Code zum Generieren von Kombinationen aus einer Anzahl von n-Arrays mit einer Anzahl von m-Elementen in JavaScript. Ich habe ähnliche Fragen dazu für andere Sprachen gesehen, aber die Antworten beinhalten syntaktische oder Bibliotheksmagie, bei der ich mir nicht sicher bin, wie ich sie übersetzen soll.

Betrachten Sie diese Daten:

[[0,1], [0,1,2,3], [0,1,2]]

3 Arrays mit einer unterschiedlichen Anzahl von Elementen. Ich möchte alle Kombinationen erhalten, indem ich ein Element aus jedem Array kombiniere.

Zum Beispiel:

0,0,0 // item 0 from array 0, item 0 from array 1, item 0 from array 2
0,0,1
0,0,2
0,1,0
0,1,1
0,1,2
0,2,0
0,2,1
0,2,2

Und so weiter.

Wenn die Anzahl der Arrays festgelegt wäre, wäre es einfach, eine fest codierte Implementierung vorzunehmen. Die Anzahl der Arrays kann jedoch variieren:

[[0,1], [0,1]]
[[0,1,3,4], [0,1], [0], [0,1]]

Jede Hilfe wäre sehr willkommen.

Hier ist eine recht einfache und kurze mit einer rekursiven Hilfsfunktion:

function cartesian(...args) {
    var r = [], max = args.length-1;
    function helper(arr, i) {
        for (var j=0, l=args[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(args[i][j]);
            if (i==max)
                r.push(a);
            else
                helper(a, i+1);
        }
    }
    helper([], 0);
    return r;
}

Verwendungszweck:

cartesian([0,1], [0,1,2,3], [0,1,2]);

Damit die Funktion ein Array von Arrays übernimmt, ändern Sie einfach die Signatur in function cartesian(args) anstatt die rest-Parametersyntax zu verwenden.

Sie könnten einen iterativen Ansatz wählen, indem Sie Unterarrays erstellen.

var parts = [[0, 1], [0, 1, 2, 3], [0, 1, 2]],
    result = parts.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; }

Ich schlage eine einfache Rekursion vor Generatorfunktion:

// Generate all combinations of array elements:
function* cartesian(head, ...tail) {
  let remainder = tail.length ? cartesian(...tail) : [[]];
  for (let r of remainder) for (let h of head) yield [h, ...r];
}


// Example:
for (let c of cartesian([0,1], [0,1,2,3], [0,1,2])) {
  console.log(...c);
}

Nachdem ich ein wenig recherchiert hatte, entdeckte ich eine frühere verwandte Frage: Alle Kombinationen von JavaScript-Array-Werten finden

Ich habe einen Teil des Codes von dort angepasst, sodass er ein Array von Arrays zurückgibt, das alle Permutationen enthält:

function(arraysToCombine) {
    var divisors = [];
    for (var i = arraysToCombine.length - 1; i >= 0; i--) {
       divisors[i] = divisors[i + 1] ? divisors[i + 1] * arraysToCombine[i + 1].length : 1;
    }

    function getPermutation(n, arraysToCombine) {
       var result = [], 
           curArray;    
       for (var i = 0; i < arraysToCombine.length; i++) {
          curArray = arraysToCombine[i];
          result.push(curArray[Math.floor(n / divisors[i]) % curArray.length]);
       }    
       return result;
    }

    var numPerms = arraysToCombine[0].length;
    for(var i = 1; i < arraysToCombine.length; i++) {
        numPerms *= arraysToCombine[i].length;
    }

    var combinations = [];
    for(var i = 0; i < numPerms; i++) {
        combinations.push(getPermutation(i, arraysToCombine));
    }
    return combinations;
}

Ich habe eine Arbeitskopie bei gestellt http://jsfiddle.net/7EakX/ das nimmt das Array, das Sie zuvor angegeben haben ([[0,1], [0,1,2,3], [0,1,2]]) und gibt das Ergebnis an die Browserkonsole aus.

Nur zum Spaß, hier ist eine funktionalere Variante der Lösung in meiner ersten Antwort:

function cartesian() {
    var r = [], args = Array.from(arguments);
    args.reduceRight(function(cont, factor, i) {
        return function(arr) {
            for (var j=0, l=factor.length; j<l; j++) {
                var a = arr.slice(); // clone arr
                a[i] = factor[j];
                cont(a);
            }
        };
    }, Array.prototype.push.bind(r))(new Array(args.length));
    return r;
}

Alternativ können wir für volle Geschwindigkeit unsere eigenen Loops dynamisch kompilieren:

function cartesian() {
    return (cartesian.cache[arguments.length] || cartesian.compile(arguments.length)).apply(null, arguments);
}
cartesian.cache = [];
cartesian.compile = function compile(n) {
    var args = [],
        indent = "",
        up = "",
        down = "";
    for (var i=0; i<n; i++) {
        var arr = "$"+String.fromCharCode(97+i),
            ind = String.fromCharCode(105+i);
        args.push(arr);
        up += indent+"for (var "+ind+"=0, l"+arr+"="+arr+".length; "+ind+"<l"+arr+"; "+ind+"++) {\n";
        down = indent+"}\n"+down;
        indent += "  ";
        up += indent+"arr["+i+"] = "+arr+"["+ind+"];\n";
    }
    var body = "var res=[],\n    arr=[];\n"+up+indent+"res.push(arr.slice());\n"+down+"return res;";
    return cartesian.cache[n] = new Function(args, body);
}

var f = function(arr){
    if(typeof arr !== 'object'){
        return false;
    }

    arr = arr.filter(function(elem){ return (elem !== null); }); // remove empty elements - make sure length is correct
    var len = arr.length;

    var nextPerm = function(){ // increase the counter(s)
        var i = 0;

        while(i < len)
        {
            arr[i].counter++;

            if(arr[i].counter >= arr[i].length){
                arr[i].counter = 0;
                i++;
            }else{
                return false;
            }
        }

        return true;
    };

    var getPerm = function(){ // get the current permutation
        var perm_arr = [];

        for(var i = 0; i < len; i++)
        {
            perm_arr.push(arr[i][arr[i].counter]);
        }

        return perm_arr;
    };

    var new_arr = [];

    for(var i = 0; i < len; i++) // set up a counter property inside the arrays
    {
        arr[i].counter = 0;
    }

    while(true)
    {
        new_arr.push(getPerm()); // add current permutation to the new array

        if(nextPerm() === true){ // get next permutation, if returns true, we got them all
            break;
        }
    }

    return new_arr;
};