up vote 3 down vote favorite
share [g+] share [fb]

How can I produce all of the permutations 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 permutations 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"]
link|improve this question
95% accept rate
Is this homework? – Alex Dec 2 '10 at 2:21
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 :) – yahelc 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. – yahelc Dec 2 '10 at 2:34
feedback

3 Answers

up vote 0 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.

link|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=... – yahelc Dec 2 '10 at 2:55
Did you mean to do ` var allCasesOfRest = allPossibleCases(arr.slice(1));` – yahelc 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. – yahelc Dec 2 '10 at 3:18
I'm accepting this answer, and am posting my 'working' version. – yahelc Dec 2 '10 at 3:21
show 1 more comment
feedback
up vote 2 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;
}
link|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 Green 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)? – David 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? – David Apr 14 '11 at 12:10
show 2 more comments
feedback
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.

link|improve this answer
feedback

Your Answer

 
or
required, but never shown

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