r - 如何在没有不必要溢出的情况下计算大阶乘的比率？

Question

我正在编写一个程序(在 R 中，以防万一)，我需要在其中计算元素向量的唯一排列数，其中可以包含重复值。 mathematical formula因为这很简单:元素总数的阶乘除以每个唯一元素的计数的阶乘的乘积。然而，即使实际答案不是很大，天真地计算结果也很可能导致溢出。例如:

# x has 200 elements, but 199 of them are identical
x <- c(rep(1, 199), 2)
num_unique_permutations <- factorial(length(x)) / prod(factorial(table(x)))

如果这没有溢出，那么 num_unique_permutations 将是 200!/(199!*1!) = 200。但是，两者都是 200!和199!溢出 double 的最大值，因此实际结果为 NaN。只要答案本身不溢出，是否有一种好的方法可以始终避免溢出(或下溢)？ (或者，只要它不在溢出的 length(x) 因素之内？)

---

(请注意，R 在大多数数值计算中使用 double ，但问题并非特定于 double 。任何具有范围的数字类型都有相同的问题。另外，我不在乎 float 会失去一点精度数学，因为我只是用它来获得某事的粗略上限。)

Answer 1

在基数 R 中，使用 lfactorial 计算分子和分母的对数。然后对适当的差取幂。

numer <- lfactorial(length(x))
denom <- sum(lfactorial(table(x)))
exp(numer - denom)
#[1] 200

这可以很容易地写成一个函数。

num_unique_permutations <- function(x){
  numer <- lfactorial(length(x))
  denom <- sum(lfactorial(table(x)))
  exp(numer - denom)
}

num_unique_permutations(x)
#[1] 200