JavaScript - Generierung von Kombinationen aus n-Reihen mit m-Elementen

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

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

Verwendung:

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

Um die Funktion nutzen ein array von arrays, ändern Sie einfach die Signatur zu function cartesian(arg) so dass arg ist ein parameter, der anstelle von alle arguments.

InformationsquelleAutor Bergi

Nur zum Spaß, hier ist eine funktionale 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;
}

Alternative, für volle Geschwindigkeit können wir dynamisch kompilieren unserer eigenen loops:

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

InformationsquelleAutor Bergi

Hier ist ein weiterer Weg, es zu tun. Ich behandle die Indizes aller arrays wie eine Zahl, deren Ziffern alle Verschieden Basen (wie z.B. Zeit und Datum), über die Länge des Arrays als die radix.

So, mit Ihrem ersten Satz von Daten, die erste Ziffer ist die Basis 2, die zweite Basis ist 4 und die Dritte base 3. Der Zähler beginnt mit 000, dann geht 001, 002, dann 010. Die Ziffern entsprechen die Indizes in den arrays, und da die Reihenfolge bewahrt wird, ist dies kein problem.

Ich habe eine Geige mit ihm, hier zu arbeiten: http://jsfiddle.net/Rykus0/DS9Ea/1/

und hier ist der code:

//Arbitrary base x number class 
var BaseX = function(initRadix){
    this.radix     = initRadix ? initRadix : 1;    
    this.value     = 0;
    this.increment = function(){
        return( (this.value = (this.value + 1) % this.radix) === 0);
    }
}

function combinations(input){
    var output    = [],    //Array containing the resulting combinations
        counters  = [],    //Array of counters corresponding to our input arrays
        remainder = false, //Did adding one cause the previous digit to rollover?
        temp;              //Holds one combination to be pushed into the output array

    //Initialize the counters
    for( var i = input.length-1; i >= 0; i-- ){
        counters.unshift(new BaseX(input[i].length));
    }

    //Get all possible combinations
    //Loop through until the first counter rolls over
    while( !remainder ){
        temp      = [];   //Reset the temporary value collection array
        remainder = true; //Always increment the last array counter

        //Process each of the arrays
        for( i = input.length-1; i >= 0; i-- ){
            temp.unshift(input[i][counters[i].value]); //Add this array's value to the result

            //If the counter to the right rolled over, increment this one.
            if( remainder ){
                remainder = counters[i].increment();
            }
        }
        output.push(temp); //Collect the results.
    }

    return output;
}

//Input is an array of arrays
console.log(combinations([[0,1], [0,1,2,3], [0,1,2]]));

InformationsquelleAutor Tom Pietrosanti