由于阶乘非常大，无法计算组合数

Question

我正在尝试计算某个数组中元素数量的组合数量。我需要确切的组合数才能将其用作要在 GPU 中执行的线程数。

但是数据很大，那么大的数，任何数据类型都无法计算阶乘

有没有一种不用求阶乘就可以计算组合数的方法？或者更有效的方法？

问题总结：

int no_of_combinations = combination(500,2);
public static int factorial(int m)
{
        int x = 1;

        for (int i = m; i > 0; i--)
            x = x * i;

        return x;
}
public static int combination(int m, int n)
{
    int x = 0;
    x = factorial(m) / (factorial(n) * factorial(m - n));
    return x;
}

Answer 1

使用帕斯卡三角形属性:

C(n,k) = C(n - 1, k) + C(n - 1, k - 1) 和动态规划。不涉及阶乘。

帕斯卡三角形是：

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

Answer 2

您需要编写一个新函数，我们将其命名为 FactorialMoverN

int FactorialMOverN(int m, int n)
{
    int x = 1;
        for (int i = m; i > n; i--)
            x = x * i;
    return x;
}

然后把你的组合函数改成

x = FactorialMOverN(m,n) * factorial(m - n));

这应该有所帮助。如果它没有帮助，那么您需要使用不同的变量类型，或者重新考虑您的问题。

感谢Sami，我看到上面的函数是错误的。 500选2需要通过

计算

int MChooseN(int m, int n)
    {
        int x = 1;
            for (int i = m; i > (m-n); i--)
                x = x * i;
        return x;
    }

上面将占用 500, 2 和 return 500*499，前面的将占用 500,2 和 returned 500*499*498...5*4*3这不是你想要的。

总之，以上就是你能得到的最好的了。

Answer 3

在这种情况下，我将开始简化等式。在您的示例中，您正在寻找 500，选择 2，即 500!/498!/2!。这个可以很方便的改成500*499/2，这样就可以算出来了

一般来说，如果你有n个选择k，你只需要计算一个"partial factorial"从n到max(k, n-k) 然后除以 min(k, n-k)! 因为结果被镜像了。这使得计算更容易。

此外，在某些情况下，您可以在乘法时开始用 min(k, n-k)! 除，但这会导致余数等。

Answer 4

您不需要使用阶乘。如果 k>n/2，则使用 C(n,k)=C(n,n-k)。然后使用 C(n,0)=1 并且对于 k>0，C(n,k) = C(n,k-1) * (n-k+1)/k。这使您可以计算几乎与动态规划方法一样多的二项式系数，但它需要线性时间 (Theta(min(n-k,k))) 和常数 space 而不是二次时间和线性 space。

查看过去的问题：How to efficiently calculate a row in pascal's triangle?

public static long combination(int n, int k)
{
  if (n-k < k)
    return combination(n,n-k);
  if (k < 0)
    return 0;
  long result = 1;
  for (int i=1; i<=k; i++)
  {
    result *= n-i+1;
    result /=i;
  } 
  return result;
}

如果回答次数n超过最大长度，这可能会溢出。因此，如果您希望答案适合 32 位 int 而您有 64 位 long，那么这不应该溢出。为避免溢出，请使用 BigIntegers 而不是 longs。

由于阶乘非常大，无法计算组合数

Unable to calculate number of combinations due to very large factorial

c#

algorithm

combinations

factorial