重复排列:避免溢出
背景:
给定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 吗?
Background:
Given n
balls such that:
'a' balls are of colour GREEN
'b' balls are of colour BLUE
'c' balls are of colour RED
...
(of course a + b + c + ... = n
)
The number of permutations in which these balls can be arranged is given by:
perm = n! / (a! b! c! ..)
Question 1:
How can I 'elegantly' calculate perm
so as to avoid an integer overflow as as long as possible, and be sure that when I am done calculating, I either have the correct value of perm
, or I know that the final result will overflow?
Basically, I want to avoid using something like GNU GMP.
Optionally, Question 2:
Is this a really bad idea, and should I just go ahead and use GMP?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
这些被称为多项式系数,我将用 m(a,b,...) 表示。
您可以通过利用这个恒等式(这应该很容易证明)来有效地计算它们,避免溢出:
然后使用递归来计算系数就很简单了。请注意,为了避免指数运行时间,您需要缓存结果(以避免重新计算)或使用动态编程。
要检查是否溢出,只需确保总和不会溢出即可。
是的,使用任意精度库来完成这个简单的任务是一个非常糟糕的主意。
These are known as the multinomial coefficients, which I shall denote by
m(a,b,...)
.And you can efficiently calculate them avoiding overflow by exploiting this identity (which should be fairly simple to prove):
Then it's a simple matter of using recursion to calculate the coefficients. Note that to avoid an exponential running time, you need to either cache your results (to avoid recomputation) or use dynamic programming.
To check for overflow, just make sure the sums won't overflow.
And yes, it's a very bad idea to use arbitrary precision libraries to do this simple task.
如果你有大量的CPU时间,你可以将所有阶乘列出来,然后找到列表中所有数字的素因数分解,然后将顶部的所有数字与底部的数字相消,直到数字完全消失减少。
If you have globs of cpu time, you can make lists out of all the factorials, then find the prime factorization of all the numbers in the lists, then cancel all the numbers on the top with those on the bottom, until the numbers are completely reduced.
最安全的溢出方式是戴夫建议的方式。您可以找到素数
p
除以n!
所得的指数,然后减去
a!a! 因式分解中
等等。对所有素数p
的指数<= n
执行此操作,即可对多项系数进行因式分解。当且仅当最终结果溢出时,该计算才会溢出。但多项式系数增长得相当快,因此对于相当小的n
,您已经出现了溢出。对于大量计算,您将需要一个 bignum 库(如果您不需要精确的结果,您可以使用 double 来获得更长的时间)。即使您使用 bignum 库,保持中间结果不会变得太大也是值得的,因此与其计算阶乘并除以巨大的数字,不如按顺序计算各个部分,
并计算每个因子,让我们以第二个为例,
计算方法是
最后将各部分相乘。这需要
n
次除法和n + number_of_parts - 1
次乘法,使中间结果保持适度较小。The overflow-safest way is the way Dave suggested. You find the exponent with which the prime
p
dividesn!
by the summationSubtract the exponents of
p
in the factorisations ofa!
etc. Do that for all primes<= n
, and you have the factorisation of the multinomial coefficient. That calculation overflows if and only if the final result overflows. But the multinomial coefficients grow rather fast, so you will have overflow already for fairly smalln
. For substantial calculations, you will need a bignum library (if you don't need exact results, you can get by a bit longer usingdouble
s).Even if you use a bignum library, it is worthwhile to keep intermediate results from getting too large, so instead of calculating the factorials and dividing huge numbers, it is better to calculate the parts in sequence,
and to compute each of these factors, let's take the second for illustration,
is calculated with
Finally multiply the parts. This requires
n
divisions andn + number_of_parts - 1
multiplications, keeping the intermediate results moderately small.根据此链接,您可以将多项式系数计算为多个二项式系数的乘积,控制整数溢出途中。
这将原始问题简化为二项式系数的溢出控制计算。
According to this link, you can calculate multinomial coefficients as a product of several binomial coefficients, controlling integer overflow on the way.
This reduces original problem to overflow-controlled computation of a binomial coefficient.
符号:
n! = prod(1,n)
其中 prod 您可能会猜到它的作用。这很简单,但首先您必须知道,对于任何 2 个正整数
(i, n > 0)
,该表达式都是正整数:因此,我们的想法是对
n 的计算进行切片!
分成小块并尽快分割。使用
a
,比使用b
等等。这些因子中的每一个都是一个整数,因此如果
perm
不会溢出,那么它的任何一个因子都不会溢出。虽然,在计算此类因子时可能会出现分子或分母溢出,但是可以避免先进行分子乘法,然后交替进行除法:
这样每次除法都会产生一个整数。
Notations:
n! = prod(1,n)
where prod you may guess what does.It's very easy, but first you must know that for any 2 positive integers
(i, n > 0)
that expression is a positive integer:Thus the idea is to slice the computation of
n!
in small chunks and to divide asap.With
a
, than withb
and so on.Each of these factors is an integer, so if
perm
will not overflow, neither one of its factors will do.Though, in the calculation of a such factor could be an overflow in numerator or denominator but that's avoidable doing a multiplication in numerator then a division in alternance:
In that way every division will yield an integer.