Efficient algorithm to get the combinations of all items in object

Viewed 857

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)

4 Answers
Related