I'm trying to write an algorithm to get all the possible combinations of N elements inside a multi dimensional array of M elements.
Something like:
function getCombinations(arr, n){
...
}
var arr = [ ["A"],["B","C"],["D","E"]];
var n = 2;
getCombinations(arr,n);
This should produce:
[
["A","B"],["A","C"],["A","D"],["A","E"],
["B","D"],["B","E"],
["C","D"],["C","E"]
]
The number of elements inside the array may vary, the only thing set is the number of elements of the combinations.
The order doesn't matter but you cannot repeat, I mean ["A","B"] == ["B","A"], so the second one is not take in consideration.
Any help?
ChrisB solution had a mistake, he wasn't caching the length of the loop before the arr.shift, and it was not returning the last combination, I think this will do the job:
function getCombinations (arr, n) {
var i, j, k, elem, l = arr.length, childperm, ret = [];
if (n == 1){
for (i = 0; i < arr.length; i++) {
for (j = 0; j < arr[i].length; j++) {
ret.push([arr[i][j]]);
}
}
return ret;
}
else {
for (i = 0; i < l; i++) {
elem = arr.shift();
for (j = 0; j < elem.length; j++) {
childperm = getCombinations(arr.slice(), n-1);
for (k = 0; k < childperm.length; k++) {
ret.push([elem[j]].concat(childperm[k]));
}
}
}
return ret;
}
}
getCombinations([["A"],["B"],["C","D"]], 2);
// [["A", "B"], ["A", "C"], ["A", "D"], ["B", "C"], ["B", "D"]]
getCombinations([["A"],["B"],["C"],["D"]], 2);
// [["A", "B"], ["A", "C"], ["A", "D"], ["B", "C"], ["B", "D"], ["C", "D"]]
Updated
Per your restriction that elements that are contained in the same array in the beginning cannot be combined I've modified the algorithm to the following:
Here is the updated jsfiddle that now even outputs the data in the correct format :) http://jsfiddle.net/QKg2H/7/
function getCombinations(arr, n)
{
if(n == 1)
{
var ret = [];
for(var i = 0; i < arr.length; i++)
{
for(var j = 0; j < arr[i].length; j++)
{
ret.push([arr[i][j]]);
}
}
return ret;
}
else
{
var ret = [];
for(var i = 0; i < arr.length; i++)
{
var elem = arr.shift();
for(var j = 0; j < elem.length; j++)
{
var childperm = getCombinations(arr.slice(), n-1);
for(var k = 0; k < childperm.length; k++)
{
ret.push([elem[j]].concat(childperm[k]));
}
}
}
return ret;
}
}
The algorithm is still recursive, but now it will consider each of the second degree elements in turn, but not with each other. Other than that, it still pops off one element and then appends the permutations of all of the remaining elements. I hope it's straightforward.
