-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循环从to ， setting的范围内(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, 与外部循环的常数相乘，count总共得到 1162334880 个增量。

允许在这里进行简单计算的关键事实是

 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

或者，如果您想从两个不同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 回答