重复排列:避免溢出

背景:

鉴于n球,使得:

 'a' balls are of colour GREEN 'b' balls are of colour BLUE 'c' balls are of colour RED ... 

(当然a + b + c + ... = n

可以安排这些球的排列数量由下式给出:

 perm = n! / (a! b! c! ..) 

问题1:我如何“优雅地”计算perm以尽可能避免整数溢出,并确保当我完成计算时,我要么具有正确的perm值,要么我知道最终结果会溢出吗?

基本上,我想避免使用像GNU GMP这样的东西。

可选地,问题2:这是一个非常糟糕的主意,我应该继续使用GMP吗?

如果你有cpu时间的全局,你可以从所有阶乘中列出列表,然后找到列表中所有数字的素数因子化,然后取消顶部的所有数字与底部的数字,直到数字完全降低。

这些被称为多项式系数,我将用m(a,b,...)

并且您可以通过利用此身份(这应该相当简单地certificate)来有效地计算它们以避免溢出:

 m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ... m(0,0,0,...) = 1 // base case m(anything negative) = 0 // base case 2 

然后,使用递归来计算系数是一件简单的事情。 请注意,为避免指数运行时间,您需要缓存结果(以避免重新计算)或使用动态编程。

要检查溢出,只需确保总和不会溢出。

是的,使用任意精度库来完成这个简单的任务是一个非常糟糕的主意。

溢出最安全的方式是戴夫建议的方式。 你找到素数p除以n!的指数n! 通过总和

 m = n; e = 0; do{ m /= p; e += m; }while(m > 0); 

在a的因子中减去p的指数a! 对所有素数<= n ,并且您具有多项式系数的因子分解。 当且仅当最终结果溢出时,该计算才会溢出。 但是多项式系数增长得相当快,因此对于相当小的n ,你已经有溢出。 对于大量计算,您将需要一个bignum库(如果您不需要精确的结果,则可以使用double s获得更长的时间)。

即使您使用bignum库,也值得保持中间结果不会过大,因此不要计算因子并划分大数,最好按顺序计算零件,

 n!/(a! * b! * c! * ...) = n! / (a! * (na)!) * (na)! / (b! * (nab)!) * ... 

并计算这些因素中的每一个,让我们以第二个为例进行说明,

 (na)! / (b! * (nab)!) = \prod_{i = 1}^b (n-a+1-i)/i 

是用。计算的

 prod = 1 for i = 1 to b prod = prod * (n-a+1-i) prod = prod / i 

最后将零件相乘。 这需要n除法和n + number_of_parts - 1乘法,保持中间结果适度小。

根据此链接 ,您可以将多项式系数计算为几个二项式系数的乘积,从而控制整数溢出。

这将原始问题减少到二项式系数的溢出控制计算。

符号: n! = prod(1,n) n! = prod(1,n)你可能猜到了什么。

这很容易,但首先你必须知道,对于任何2个正整数(i, n > 0) ,表达式是一个正整数:

 prod(i,i+n-1)/prod(1,n) 

因此,想法是切片n!的计算n! 在小块中,尽快分开。

a ,比用b等。

 perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!) 

这些因素中的每一个都是整数,所以如果perm不会溢出,那么它的一个因素都不会。

虽然,在计算这样一个因子时,可能是分子或分母的溢出但是可以避免在分子中进行乘法,然后是交替的除法:

 prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b 

这样每个分区都会产生一个整数。