array combos

Benchmark created by Max on June 15, 2015

Setup

arr = [[0,1], [0,1,2,3], [0,1,2]];
    
    function combine1(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;
    };
    
    function combine2(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;
    }
    
    // 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 combine3(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;
    }
    
    function combine4() {
        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;
    }

Test runner

combine1(arr);

combine2(arr);

combine3(arr);

combine4(arr);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by Max on June 15, 2015