计算组合数量 - 替代方法？

Question

虽然有众所周知的、稳定的、鲁棒的计算组合的算法， 我承认它的价值，但它只停留在完整的区域。我们还知道 nCr = n!/(r!*(n-r)!)。 受此启发，我为它设计了 C++ 解决方案；

#include <cmath>
using namespace std; //For brevity here; I know this is bad practice in general

double solution (double n, double r){
    return exp(lgamma(n) - lgamma(r) -lgamma(n-r));
}

原则上，由于它是数学上合法的公式，它应该有效。然而，它有时会产生错误的答案。在我看来，浮点精度问题就是造成这种情况的原因。是否有一些改进这种替代方法的秘诀？

编辑：我注意到 gamma(x) = (x-1)！所以..解决这个问题的一种方法可能是这样的：

#include <cmath>
using namespace std; //For brevity here; I know this is bad practice in general

double solution (double n, double r){
    return exp(lgamma(n+1) - lgamma(r+1) -lgamma(n-r+1));
}

Answer 1

就其价值而言，这里是组合“n 选择 k”函数的简单精确 C 实现，适用于小 n。同样的想法可以扩展到更大的整数类型。如果存在无效输入或发生溢出，则返回零。

uint64_t nchoosek(uint64_t n, uint64_t k) {
  // No overflow for n <= 62.
  if (n == 0) return 0;
  if (k > n) return 0;
  if ((k == 0) || (k == n)) return 1;
  if (n-k < k) k = n-k;
  uint64_t res = n;
  for (uint32_t i=2; i<=k; i++) {
    uint64_t temp = n-i+1;
    if (res > 0xffffffffffffffffULL / temp) return 0; // Overflow check
    res = (res*temp)/i;
  }
  return res;
}