JavaScript - Generating combinations from n arrays

Question

I'm having trouble coming up with code to generate combinations from n number of arrays with m number of elements in them, in JavaScript. I've seen similar questions about this for other languages, but the answers incorporate syntactic or library magic that I'm unsure how to translate.

Consider this data:

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

3 arrays, with a different number of elements in them. What I want to do is get all combinations by combining an item from each array.

For example:

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

And so on.

If the number of arrays were fixed, it would be easy to make a hard coded implementation. But the number of arrays may vary:

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

Any help would be much appreciated.

Answer 1

Here's another way of doing it. I treat the indices of all of the arrays like a number whose digits are all different bases (like time and dates), using the length of the array as the radix.

So, using your first set of data, the first digit is base 2, the second is base 4, and the third is base 3. The counter starts 000, then goes 001, 002, then 010. The digits correspond to indices in the arrays, and since order is preserved, this is no problem.

I have a fiddle with it working here: http://jsfiddle.net/Rykus0/DS9Ea/1/

and here is the 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]]));

Answer 2

I suggest a simple recursive generator function:

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