-1

メソッドの可能な組み合わせの合計を計算する最も簡単な方法は何ですか? これは、私が解決しようとしているクラスの例です。

class Combinations {

    public void generate()
    {
        final int TOTAL_A = 10;
        final int TOTAL_B = 21; // TOTAL_B is used twice
        final int TOTAL_C = 17;
        final int TOTAL_Z = 20;
        int count = 0;
        for (int a = 0; a < TOTAL_A; a++)
        {
            for (int b = 0; b < TOTAL_B; b++)
            {
                for (int b_two = 0; b_two < TOTAL_B; b_two++)
                {
                    for (int c = 0; c < TOTAL_C; c++)
                    {
                        for (int one = 0; one < TOTAL_Z; one++)
                            for (int two = one + 1; two < TOTAL_Z; two++)
                                for (int three = two + 1; three < TOTAL_Z; three++)
                                    for (int four = three + 1; four < TOTAL_Z; four++)
                                        for (int five = four + 1; five < TOTAL_Z; five++)
                                            count++;
                    }
                }
            }
        }
        System.out.println("Total combinations: " + count);
    }

}

実際にループを実行することなく、「カウント」が何であるかを把握する方法は何でしょうか?

4

2 に答える 2

0

外側のループa, b, b_two, cは、内側のループで行われることにまったく影響を与えないため、繰り返しの係数を生成するだけです。

TOTAL_A * TOTAL_B² * TOTAL_C

内側のループの仕事で乗算します。

内側のループは、one, two, three, four, five他のループに影響を与えたり依存したりします。各ループは囲まれたループの範囲を決定するので、自然に裏返しに作業します。

for (int five = four + 1; five < TOTAL_Z; five++)
     count++;

そのため、最も内側のループcountは合計TOTAL_Z - 1 - four回増加します。簡潔TOTAL_Z - 1にするために で表すことにしましょう。N

fourループは

N - four

fourからthree+1までNの増分

    N             N-three-1
    ∑ (N - four) =    ∑ k    = (N-three)*(N-three-1)/2
four=three+1         k=0

threeループはからまでの範囲で(N-three)*(N-three-1)/2インクリメントします。を与える設定threetwo+1Nj = N - three

N-two-1
  ∑    j*(j-1)/2 = (N-two)*(N-two-1)*(N-two-2)/6
 j=0

twoループはからまでの範囲で(N-two)*(N-two-1)*(N-two-2)/6インクリメントを行い、 を設定します。twoone+1Nj = N - two

N-one-1
   ∑   j*(j-1)*(j-2)/6 = (N-one)*(N-one-1)*(N-one-2)*(N-one-3)/24
  j=0

最後に、ループは0 から までの範囲oneで上記の量のインクリメントを行い、oneN

   N                                            N
   ∑ (N-one)*(N-one-1)*(N-one-2)*(N-one-3)/24 = ∑ k*(k-1)*(k-2)*(k-3)/24
one=0                                          k=0
                                              =  (N+1)*N*(N-1)*(N-2)*(N-3)/120

(または(N+1) `choose` 5) 内側のループで一緒にインクリメントします。

N = TOTAL_Z - 1 = 19、20 `choose` 5 = 15504、外側のループの定数で乗算すると、合計で 1162334880 の増分が得られますcount。

ここで簡単な計算を可能にする重要な事実は、

 m
 ∑   (n+k) `choose` k = (n+m+1) `choose` m
k=0
于 2012-12-17T19:36:53.760 に答える
0 
|A| * (|B| choose 2) * |C| * (|Z| choose 5) = 553,492,800

または、同じサイズの2 つの異なるプールから選択する場合B1:B2

|A| * |B1| * |B2| * |C| * (|Z| choose 5) = 1,162,334,880

はn choose k次のように定義されます。

n!/(k!*(n-k)!)
于 2012-12-17T21:29:01.290 に答える