Geek Answers Handbook

Get all combinations of N elements of a multidimensional array

I am trying to write an algorithm to get all possible combinations of N elements inside a multidimensional 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 can vary, the only thing that is established is the number of elements in combinations.

The order does not matter, but you cannot repeat, I mean ["A","B"] == ["B","A"] , so the second is not taken into account.

Any help?

+3
javascript combinations
source share
2 answers

ChrisB's solution had an error, he did not take the length of the loop before arr.shift, and he did not return the last combination, so I think this will complete the task:

 function getCombinations(arr, n){ var i,j,k,elem,l = arr.length,childperm,ret=[]; if(n == 1){ 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{ 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; } i=j=k=elem=l=childperm=ret=[]=null; } getCombinationss([["A"],["B"],["C","D"]], 2); //[["A", "B"], ["A", "C"], ["A", "D"], ["B", "C"], ["B", "D"]] getCombinationss([["A"],["B"],["C"],["D"]], 2); //[["A", "B"], ["A", "C"], ["A", "D"], ["B", "C"], ["B", "D"], ["C", "D"]]
+5
source share

Update

For the limitation that the elements that are contained in the same array at the beginning cannot be combined, I modified the algorithm as follows:

Here is the updated jsfiddle, which now even displays 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 elements of the second degree in turn, but not with each other. In addition, it still pushes one item, and then adds permutations of all the other items. Hope it's easy.

+2
source share

More articles:


All Articles