CODEWITHSUNDEEP
javascriptalgorithmcombinationscombinatorics
Matt Saddington
Matt Saddington

Reputation: 151

Specific combination algorithm

If I have n balls and k containers then this -> ( (n+k-1)! / n!(k-1)! ) will work out how many combinations there are.

I am having difficulty changing this to produce a list of all combinations in javascript.

In a function taking an array of balls and some amount of containers.

combinations([1,2,3,4,5,6], 3)

Each container can have any number of balls and containers can be empty.

Here is something i attempted but im only getting one ball in each container.

function generateCombinations(array, r, callback) {
    function equal(a, b) {
        for (var i = 0; i < a.length; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
    function values(i, a) {
        var ret = [];
        for (var j = 0; j < i.length; j++) ret.push(a[i[j]]);
        return ret;
    }
    var n = array.length;
    var indices = [];
    for (var i = 0; i < r; i++) indices.push(i);
    var final = [];
    for (var i = n - r; i < n; i++) final.push(i);
    while (!equal(indices, final)) {
        callback(values(indices, array));
        var i = r - 1;
        while (indices[i] == n - r + i) i -= 1;
        indices[i] += 1;
        for (var j = i + 1; j < r; j++) indices[j] = indices[i] + j - i;
    }
    callback(values(indices, array));
}
count = 0
generateCombinations([1,2,3,4,5,6,7,8,9,1],3,function(first){
             $("#hello").append(first+"<br />")
             count = count +1
})

$("#hello").append(count)

Upvotes: 1

Views: 510

Answers (2)

artahian
artahian

Reputation: 2093

You can do it in this way:

var containers = [];

// n - number of balls, k - number of containers
function dfs(n, k) {
    // Ending point of recursion, all balls are placed
    if(n == 0) {
        var output = [];
        for(var i = 0; i < k; i++) {
            output.push('{' + containers[i].join(', ') + '}');
        }
        output = '[' + output.join(', ') + ']';
        console.log(output);
        return;
    }

    // Try to put ball #n
    for(var i = 0; i < k; i++) {
        containers[i].push(n);

        // Now we have placed ball #n, so we have 1 .. n - 1 balls only
        dfs(n - 1, k);

        // Remove ball when back to use again
        containers[i].pop();
    }
}

var n = 4;
var k = 3;
for(var i = 0; i < k; i++) {
    containers[i] = [];
}
dfs(n, k);

Upvotes: 1

didierc
didierc

Reputation: 14730

I initially thought you wanted all the combinations of k elements out of n, but your problem is different, it's partitioning n elements in k parts.

When going through the elements, at each steps, you may choose to put the current element in any container, that's k possibilities. In total, you will have kn possible solutions.

Therefore, it would be faster to iterate through all the solutions, rather than storing them in an array.

You can represent a solution as a unique number in base k, with n digits, and iterate through the solutions by incrementing that number.

In your example, the base is 3, and the number of digits is 6. The first solution is to put all the balls in container 0, ie.

  000000

The next solution is to put all the balls in container 0, excepted the last which goes in container 1.

  000001

... 000002 000010 000011 000020

Hopefully you should get the idea.

Upvotes: 0

Related Questions