重复排列:避免溢出

Question

背景:

鉴于以下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吗？

Answer 1

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

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

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

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

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

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

Answer 2

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