我需要一种计算组合而不会耗尽内存的方法。这是我到目前为止所拥有的。
public static long combination(long n, long k) // nCk
{
return (divideFactorials(factorial(n), ((factorial(k) * factorial((n - k))))));
}
public static long factorial(long n)
{
long result;
if (n <= 1) return 1;
result = factorial(n - 1) * n;
return result;
}
public static long divideFactorials(long numerator, long denominator)
{
return factorial(Math.Abs((numerator - denominator)));
}
我已将其标记为 C#，但理想情况下，该解决方案应该与语言无关。
我见过的计算二项式系数的最佳方法之一是Mark Dominus。与其他一些方法相比，使用较大的 N 和 K 值溢出的可能性要小得多。
public static long GetBinCoeff(long N, long K)
{
// This function gets the total number of unique combinations based upon N and K.
// N is the total number of items.
// K is the size of the group.
// Total number of unique combinations = N! / ( K! (N - K)! ).
// This function is less efficient, but is more likely to not overflow when N and K are large.
// Taken from: http://blog.plover.com/math/choose.html
//
long r = 1;
long d;
if (K > N) return 0;
for (d = 1; d <= K; d++)
{
r *= N--;
r /= d;
}
return r;
}
这是一个与 Bob Byran 非常相似的解决方案，但检查了另外两个前提条件以加快代码速度。
/// <summary>
/// Calculates the binomial coefficient (nCk) (N items, choose k)
/// </summary>
/// <param name="n">the number items</param>
/// <param name="k">the number to choose</param>
/// <returns>the binomial coefficient</returns>
public static long BinomCoefficient(long n, long k)
{
if (k > n) { return 0; }
if (n == k) { return 1; } // only one way to chose when n == k
if (k > n - k) { k = n - k; } // Everything is symmetric around n-k, so it is quicker to iterate over a smaller k than a larger one.
long c = 1;
for (long i = 1; i <= k; i++)
{
c *= n--;
c /= i;
}
return c;
}
public static long combination(long n, long k)
{
double sum=0;
for(long i=0;i<k;i++)
{
sum+=Math.log10(n-i);
sum-=Math.log10(i+1);
}
return (long)Math.pow(10, sum);
}
查看您的代码，难怪您会很快耗尽内存。您的方法divideFactorials调用方法阶乘并使用差异“分子-分母”作为参数。根据您的代码，这种差异很可能会非常大，并且您将在阶乘方法中陷入很长的循环中。
如果它真的只是为了找到 nCk（我假设这是因为您在代码中的注释），只需使用：
public static long GetnCk(long n, long k)
{
long bufferNum = 1;
long bufferDenom = 1;
for(long i = n; i > Math.Abs(n-k); i--)
{
bufferNum *= i;
}
for(long i = k; i => 1; i--)
{
bufferDenom *= i;
}
return (long)(bufferNom/bufferDenom);
}
当然使用这种方法你会很快超出范围，因为 long 实际上并不支持很长的数字，所以 n 和 k 必须小于 20。
假设您实际上使用非常大的数字，您可以使用双精度数而不是长数，因为幂变得越来越重要。
编辑： 如果您使用大量数字，您也可以使用斯特林公式：
随着 n 变大 ln(n!) -> n*ln(n) - n。
将其放入代码中：
public static double GetnCk(long n, long k)
{
double buffern = n*Math.Log(n) - n;
double bufferk = k*Math.Log(k) - k;
double bufferkn = Math.Abs(n-k)*Math.Log(Math.Abs(n-k)) - Math.Abs(n-k);
return Math.Exp(buffern)/(Math.Exp(bufferk)*Math.Exp(bufferkn));
}
我只提出这个答案，正如你所说的与语言无关，C#代码只是用来演示它。由于您需要对 n 和 k 使用较大的数字才能使其起作用，因此我建议将其作为查找大型组合的二项式系数的一般方法。
对于 n 和 k 都小于 200-300 左右的情况，您应该使用 Victor Mukherjee 提出的答案，因为它是准确的。
Edit2： 编辑了我的第一个代码。