7

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?

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Javier Cobos
  • 1,172
  • 10
  • 22
  • Since the dimensions are completely ignored. You could just convert the array to 1D, and run a simple permutation algorithm over it. – Daniel Aug 14 '13 at 14:08
  • Also, take into account that with `n` different elements, it will generate `n!` permutations... it may take a while with a higher number of elements – Daniel Aug 14 '13 at 14:13
  • so just to be clear BC and DE are not valid combinations? because they are not in your example. IN which case it is not a simple permutation. Similarly if n=3 is ABC a valid combination? – Shaunak Aug 14 '13 at 14:17
  • Sorry but its not like that, see 3º answer to furder instructions – Javier Cobos Aug 14 '13 at 18:40

2 Answers2

11

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"]]
Jonathan
  • 32,202
  • 38
  • 137
  • 208
Javier Cobos
  • 1,172
  • 10
  • 22
  • Oops sorry about the bug. Glad it at least got you on the right path. – Chris B Aug 15 '13 at 12:17
  • Thanks so much Chris B, I got stuck ;), you drove me to the correct way :). – Javier Cobos Aug 16 '13 at 06:36
  • Thank you very much for the useful snippet @JavierCobos. I need to keep the positions also of the elements and do some action with them. Any way how i can keep the position also of the elements inside combinations? Thanks in advance – Ana DEV Oct 04 '17 at 06:27
3

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.

Chris B
  • 733
  • 3
  • 10
  • Realized I'm not returning the values in the same format you specified, but it shouldn't be too hard to modify the code to fit. – Chris B Aug 14 '13 at 15:06
  • Nope its not working properly, for example: getCombinations([["A"],["B"],["C"],["D"]], 2); Returns [["A", "B"], ["A", "C"], ["A", "D"], ["B", "C"], ["B", "D"]] Its not retrieving ["C","D"] – Javier Cobos Aug 15 '13 at 09:43
  • I fixed it and posted down – Javier Cobos Aug 15 '13 at 10:34