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

Question

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

# 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在大多数数值计算中使用doubles，但这个问题并不是doubles特有的。任何有范围的数字类型都有同样的问题。此外，我不在乎浮点数学会损失一点精度，因为我只是用它来获得一些东西的粗略上限。(

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

Answer 2

您可以使用gmp库。

library(gmp)
factorial(as.bigz(length(x))) / prod(factorial(as.bigz(table(x))))
#[1] 200