1

如果我有 n 个球和 k 个容器，那么这个 -> ( (n+k-1)! / n!(k-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)
4

2 回答 2

1

你可以这样做：

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);
于 2013-03-06T10:05:46.133 回答
0

我最初以为您想要 n 中 k 元素的所有组合，但您的问题不同，它将 n 元素划分为 k 部分。

在遍历元素时，在每个步骤中，您都可以选择将当前元素放入任何容器中，这是k可能的。总的来说，您将有 k n 个可能的解决方案。

因此，迭代所有解决方案会更快，而不是将它们存储在数组中。

您可以将解决方案表示为 base 中的唯一数字k，带有n数字，并通过增加该数字来迭代解决方案。

在您的示例中，底数为 3，位数为 6。第一个解决方案是将所有球放入容器 0 中，即。

  000000

下一个解决方案是将所有球放入容器 0 中，除了最后一个放入容器 1 中。

  000001

... 000002 000010 000011 000020

希望你应该明白这一点。

于 2013-03-06T06:56:47.143 回答