Specific combination algorithm

Обновить

April 2019

Просмотры

483 раз

1

Если у меня есть п шаров и к емкости, то это -> (!! (П + к-1) / п (к-1)) будет работать, сколько комбинаций есть.

У меня возникают трудности при изменении этого, чтобы получить список всех комбинаций в JavaScript.

В функции принимает массив шаров и некоторое количество контейнеров.

Комбинации ([1,2,3,4,5,6], 3)

Каждый контейнер может иметь любое количество шаров и контейнеры могут быть пустыми.

Вот что-то я пытался, но им только получать один мяч в каждом контейнере.

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)

2 ответы

1

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);
0

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.