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

You could use an iterative and recursive approach with stress on the length of the array and the still needed items.

Basically combine() takes an array with the values to combine and a size of the wanted combination results sets.

The inner function c() takes an array of previously made combinations and a start value as index of the original array for combination. The return is an array with all made combinations.

The first call is allways c([], 0), because of an empty result array and a start index of 0.

function combine(array, size) {

    function c(part, start) {
        var result = [], i, l, p;
        for (i = start, l = array.length; i < l; i++) {
            p = part.slice(0);                       // get a copy of part
            p.push(array[i]);                        // add the iterated element to p
            if (p.length < size) {                   // test if recursion can go on
                result = result.concat(c(p, i + 1)); // call c again & concat rresult
            } else {
                result.push(p);                      // push p to result, stop recursion
            }
        }
        return result;
    }

    return c([], 0);
}

console.log(combine(["a", "b", "c", "d"], 3));

.as-console-wrapper { max-height: 100% !important; top: 0; }