由于Factorial溢出导致的组合问题

本文关键字：组合 问题 Factorial 溢出 由于 | 更新日期: 2023-09-27 18:14:57

我需要一个可以计算纸牌游戏中(n, k)的数学组合的函数。

我目前的尝试是使用一个基于通常的Factorial方法的函数:

    static long Factorial(long n)
    {
        return n < 2 ? 1 : n * Factorial(n - 1); 
    }
    static long Combinatory(long n , long k )
    {
        return Factorial(n) / (Factorial(k) * Factorial(n - k)); 
    }

它工作得很好，但问题是，当我使用一些数字范围(n值最大值是52,k值最大值是4)，它让我返回一个错误的值。例如:

   long comb = Combinatory(52, 2) ; // return 1 which should be actually 1326

我知道这是因为我在Factorial(52)时溢出了long，但是我需要的范围结果并没有看起来那么大。

有办法解决这个问题吗?

由于Factorial溢出导致的组合问题

不使用默认的组合公式n! / (k! x (n - k)!)，而是使用组合函数的递归属性。

    (n, k) = (n - 1, k) + (n - 1, k - 1)

知道:(n, 0) = 1和(n, n) = 1。

->它将使您避免使用factorial和溢出您的long。

下面是你可以做的实现示例:

 static long Combinatory(long n, long k)
    {
        if (k == 0 || n == k )
            return 1;
        return Combinatory(n - 1, k) + Combinatory(n - 1, k - 1); 
    }

EDIT:使用更快的迭代算法

    static long Combinatory(long n, long k)
    {
        if (n - k < k)
            k = n - k;
        long res = 1;
        for (int i = 1; i <= k; ++i)
        {
            res = (res * (n - i + 1)) / i;
        }
        return res;
    }

在c#中你可以使用BigInteger(我想Java中也有类似的)。

例如:

static long Combinatory(long n, long k)
{
    return (long)(Factorial(new BigInteger(n)) / (Factorial(new BigInteger(k)) * Factorial(new BigInteger(n - k))));
}
static BigInteger Factorial(BigInteger n)
{
    return n < 2 ? 1 : n * Factorial(n - 1);
}

使用BigInteger需要添加System.Numerics的引用

如果这不是用于家庭作业，那么在Apache的commons-math包中有一个有效的实现

http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/ArithmeticUtils.html binomialCoefficientDouble % 28 int, int % 20 % 29日

如果它是一个家庭作业，在你的实现中开始避免阶乘。

使用属性(n, k) = (n, n-k)重写您的选择，使用k的最大值。

然后注意你可以约简n!/k!(n-k)!到n * n-1 * n-2 ....* k/(n-k) * (n-k-1)…* 1意味着你要乘以[k, n]中的所有数字，然后除以[1,n-k]中的所有数字。

// From memory, please verify correctness independently before trusting its use.
//
public long choose(n, k) {
  long kPrime = Math.max(k, n-k);
  long returnValue = 1;
  for(i = kPrime; i <= n; i++) {
    returnValue *= i;
  }
  for(i = 2; i <= n - kPrime; i++) {
    returnValue /= i;
  }
  return returnValue;
}

请仔细检查数学，但这是一个基本的想法，你可以去得到一个合理有效的实现，将适用于数字到扑克牌。

递归公式也被称为帕斯卡三角形，在我看来，这是计算组合数最简单的方法。如果你只需要C(52,k)(对于0<=k<=52)，我认为最好在程序开始时用它们填一个表。下面的C代码使用这个方法填充一个表:

static  int64_t*    pascals_triangle( int N)
{
int n,k;
int64_t*    C = calloc( N+1, sizeof *C);
    for( n=0; n<=N; ++n)
    {   C[n] = 1;
        for( k=n-1; k>0; --k)
        {   C[k] += C[k-1];
        }
    }
    return C;
}

调用N=52后，例如返回，C[k]将保存C(52,k)，k =0..52

相关文章：