Efficient algorithm to get the combinations of all items in object

Question

Given an array or object with n keys, I need to find all combinations with length x.
Given X is variable. binomial_coefficient(n,x).

Currently I'm using this:

function combine(items) {
    var result = [];
    var f = function(prefix, items) {
        for (var i = 0; i < items.length; i++) {
            result.push(prefix + items[i]);
            f(prefix + items[i], items.slice(i + 1));
        }
    }
    f('', items);
    return result;
}

var combinations = combine(["a", "b", "c", "d"]);

The output is:

["a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", "d"]

So if I want the binomial coefficient x=3 from n=4 I select all the strings with length equal to three. {abc, abd, acd, bcd}.

So I do this in two steps.

Is there a more efficient algorithm with smaller complexity?

Link: Solution performance (JSPerf)

Answer 1

Your algorithm is almost O(2^n), you can discard a lot of combinations, but the num of elements will be (n! * (n-x)!) / x!.

To discard the useless combinations you can use an indexed array.

 function combine(items, numSubItems) {
        var result = [];
        var indexes = new Array(numSubItems);
        for (var i = 0 ; i < numSubItems; i++) {
            indexes[i] = i;
        }
        while (indexes[0] < (items.length - numSubItems + 1)) {
            var v = [];
            for (var i = 0 ; i < numSubItems; i++) {
                v.push(items[indexes[i]]);
            }
            result.push(v);
            indexes[numSubItems - 1]++;
            var l = numSubItems - 1; // reference always is the last position at beginning
            while ( (indexes[numSubItems - 1] >= items.length) && (indexes[0] < items.length - numSubItems + 1)) {
                l--; // the last position is reached
                indexes[l]++;
                for (var i = l +1 ; i < numSubItems; i++) {
                    indexes[i] = indexes[l] + (i - l);
                }
            }        
        }
        return result;
    }

    var combinations = combine(["a", "b", "c", "d"], 3);
    console.log(JSON.stringify(combinations));

For example, the first combination have the indexes: [0, 1, 2] and the elements ["a", "b", "c"]. To compute the next combination, It get the last index 2 and try to increment, if the increment is lower than the max position (in this case 4), the next combination is reached, but if It is not, It must increment to a previous index.