current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 7 down vote favorite
5

How can I produce all of the combinations of the values in N number of JavaScript arrays of variable lengths?

Let's say I have N number of JavaScript arrays, e.g.

var first = ['a', 'b', 'c', 'd'];
var second = ['e'];
var third =  ['f', 'g', 'h', 'i', 'j'];

(Three arrays in this example, but its N number of arrays for the problem.)

And I want to output all the combinations of their values, to produce

aef
aeg
aeh
aei
aej
bef
beg
....
dej

EDIT: Here's the version I got working, using ffriend's accepted answer as the basis.

var allArrays = [['a', 'b'], ['c', 'z'], ['d', 'e', 'f']];

 function allPossibleCases(arr) {
  if (arr.length === 0) {
    return [];
  } 
else if (arr.length ===1){
return arr[0];
}
else {
    var result = [];
    var allCasesOfRest = allPossibleCases(arr.slice(1));  // recur with the rest of array
    for (var c in allCasesOfRest) {
      for (var i = 0; i < arr[0].length; i++) {
        result.push(arr[0][i] + allCasesOfRest[c]);
      }
    }
    return result;
  }

}
var r=allPossibleCases(allArrays);
 //outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"]
share|improve this question
    
Is this homework? –  Alex Dec 2 '10 at 2:21
1  
Nope. I'm building a tool simulating multivariate for Optimizely, and realized that this is a non-trivial problem, and couldn't find a JavaScript example for this. But thanks for making me feel like an idiot :) –  Yahel Dec 2 '10 at 2:22
    
I think this is a little ill-defined. You've shown output values based on first|second|third, where one value is taken from each. Is eaf an unacceptable value? Or do you really mean that you just want strings of N length, where each character is from a different array? –  Josh Leitzel Dec 2 '10 at 2:32
    
As far as this is concerned, eaf==aef. Order doesn't matter. So, yes, I want to produce an array of strings, where each value is a string of N length, and where each character is from a different array. –  Yahel Dec 2 '10 at 2:34
    
You need to edit the title / content : you do not seek the permutations but rather the cartesian product of the sets contained within the arrays. en.wikipedia.org/wiki/Cartesian_product –  GameAlchemist Aug 18 '13 at 23:32

3 Answers 3

up vote 5 down vote accepted

This is not permutations, see permutations definitions from Wikipedia.

But you can achieve this with recursion: 

var allArrays = [['a', 'b'], ['c'], ['d', 'e', 'f']]

function allPossibleCases(arr) {
  if (arr.length == 1) {
    return arr[0];
  } else {
    var result = [];
    var allCasesOfRest = allPossibleCases(arr.slice(1));  // recur with the rest of array
    for (var i = 0; i < allCasesOfRest.length; i++) {
      for (var j = 0; j < arr[0].length; j++) {
        result.push(arr[0][j] + allCasesOfRest[i]);
      }
    }
    return result;
  }

}

You can also make it with loops, but it will be a bit tricky and will require implementing your own analogue of stack.

share|improve this answer
    
I figured this would involve recursion. 2 minor syntax points: case is a reserved word, and you're missing a semicolon on the first line. I'm not sure what's going on at var allCasesofRest=... –  Yahel Dec 2 '10 at 2:55
    
Did you mean to do ` var allCasesOfRest = allPossibleCases(arr.slice(1));` –  Yahel Dec 2 '10 at 3:01
    
You're right, fixed it. And yes, there will be recursion, but if you got the point you can rewrite it to use iteration - just "fold" an array of arrays, yielding and passing to the next iteration array of all possible combinations of previous chars. –  ffriend Dec 2 '10 at 3:14
    
Still not quite working, but I'm getting closer. –  Yahel Dec 2 '10 at 3:18
    
I'm accepting this answer, and am posting my 'working' version. –  Yahel Dec 2 '10 at 3:21
up vote 7 down vote

You don't need recursion, or heavily nested loops, or even to generate/store the whole array of permutations in memory.

Since the number of permutations is the product of the lengths of each of the arrays (call this numPerms), you can create a function getPermutation(n) that returns a unique permutation between index 0 and numPerms - 1 by calculating the indices it needs to retrieve its characters from, based on n.

How is this done? If you think of creating permutations on arrays each containing: [0, 1, 2, ... 9] it's very simple... the 245th permutation (n=245) is "245", rather intuitively, or:

arrayHundreds[Math.floor(n / 100) % 10]
+ arrayTens[Math.floor(n / 10) % 10]
+ arrayOnes[Math.floor(n / 1) % 10]

The complication in your problem is that array sizes differ. We can work around this by replacing the n/100, n/10, etc... with other divisors. We can easily pre-calculate an array of divisors for this purpose. In the above example, the divisor of 100 was equal to arrayTens.length * arrayOnes.length. Therefore we can calculate the divisor for a given array to be the product of the lengths of the remaining arrays. The very last array always has a divisor of 1. Also, instead of modding by 10, we mod by the length of the current array.

Example code is below:

var allArrays = [first, second, third, ...];

// Pre-calculate divisors
var divisors = [];
for (var i = allArrays.length - 1; i >= 0; i--) {
   divisors[i] = divisors[i + 1] ? divisors[i + 1] * allArrays[i + 1].length : 1;
}

function getPermutation(n) {
   var result = "", curArray;

   for (var i = 0; i < allArrays.length; i++) {
      curArray = allArrays[i];
      result += curArray[Math.floor(n / divisors[i]) % curArray.length];
   }

   return result;
}
share|improve this answer
    
Very nice. There is a typo here though, results should show result -- I notice you loop backwards for calculating the divisors, I assume the position of the divisor in the array is important? –  Gary Hole Apr 14 '11 at 11:05
    
@Gary, thanks for picking that up. The order of the divisors matters because the first one depends on the second, the second depends on the third, etc... So by looping backwards I can build this up more easily. –  Box9 Apr 14 '11 at 11:36
    
@Box9: Does this function works with 1 array? Isn't it (n*n) - (n-1)? –  Phpdna Apr 14 '11 at 11:53
    
@epitaph, it should still work with 1 array. divisors will only have one element: [1], and so it will always divide by 1, and mod by the array length - in effect, doing nothing. –  Box9 Apr 14 '11 at 11:57
    
If it works on 1 array and the result (n*n)-(n-1) can I use it to make a cost matrix? For example for the travelsalesman problem? –  Phpdna Apr 14 '11 at 12:10
up vote 1 down vote

Check here for some good answers: Generating All Permutations of Character Combinations when # of arrays and length of each array are unknown

Code samples aren't specific to javascript, but may be inspiring.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.