1

n個のボールとk個のコンテナがある場合、これ -> ( (n+k-1)! / n!(k-1)! ) は組み合わせがいくつあるかを計算します。

これを変更して、JavaScript ですべての組み合わせのリストを作成するのは困難です。

ボールの配列といくつかのコンテナを受け取る関数内。

組み合わせ([1,2,3,4,5,6], 3)

各コンテナには任意の数のボールを入れることができ、コンテナは空にすることができます。

これは私が試みたものですが、各コンテナにボールが1つしかありません。

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可能性です。合計で、kn個の可能な解決策があります。

したがって、すべてのソリューションを配列に格納するよりも、すべてのソリューションを反復処理する方が高速です。

解を基数の一意の数字として数字で表し、kそのn数を増やすことで解を反復処理できます。

あなたの例では、底辺は3で、桁数は6です。最初の解決策は、すべてのボールをコンテナ0に入れることです。

  000000

次の解決策は、コンテナ1に入る最後のボールを除いて、すべてのボールをコンテナ0に入れることです。

  000001

... 000002 000010 000011 000020

うまくいけば、あなたはアイデアを得る必要があります。

于 2013-03-06T06:56:47.143 に答える