我正在编写一个程序(在 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 会失去一点精度数学,因为我只是用它来获得某事的粗略上限。)
最佳答案
在基数 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
关于r - 如何在没有不必要溢出的情况下计算大阶乘的比率?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63690732/