重复排列:避免溢出

发布于 2024-12-22 05:32:03 字数 496 浏览 0 评论 0原文

背景:

给定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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

葵雨 2024-12-29 05:32:03

这些被称为多项式系数,我将用 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

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

要检查是否溢出,只需确保总和不会溢出即可。

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

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):

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

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.

深爱不及久伴 2024-12-29 05:32:03

如果你有大量的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.

岁月无声 2024-12-29 05:32:03

最安全的溢出方式是戴夫建议的方式。您可以找到素数 p 除以 n! 所得的指数,然后

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

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

即使您使用 bignum 库,保持中间结果不会变得太大也是值得的,因此与其计算阶乘并除以巨大的数字,不如按顺序计算各个部分,

n!/(a! * b! * c! * ...) = n! / (a! * (n-a)!) * (n-a)! / (b! * (n-a-b)!) * ...

并计算每个因子,让我们以第二个为例,

(n-a)! / (b! * (n-a-b)!) = \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 次乘法,使中间结果保持适度较小。

The overflow-safest way is the way Dave suggested. You find the exponent with which the prime p divides n! by the summation

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

Subtract the exponents of p in the factorisations of a! 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 small n. For substantial calculations, you will need a bignum library (if you don't need exact results, you can get by a bit longer using doubles).

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,

n!/(a! * b! * c! * ...) = n! / (a! * (n-a)!) * (n-a)! / (b! * (n-a-b)!) * ...

and to compute each of these factors, let's take the second for illustration,

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

is calculated with

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

Finally multiply the parts. This requires n divisions and n + number_of_parts - 1 multiplications, keeping the intermediate results moderately small.

北方的巷 2024-12-29 05:32:03

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

这将原始问题简化为二项式系数的溢出控制计算。

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.

小镇女孩 2024-12-29 05:32:03

符号:n! = prod(1,n) 其中 prod 您可能会猜到它的作用。

这很简单,但首先您必须知道,对于任何 2 个正整数 (i, n > 0),该表达式都是正整数:

prod(i,i+n-1)/prod(1,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

这样每次除法都会产生一个整数。

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:

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

Thus the idea is to slice the computation of n! in small chunks and to divide asap.

With a, than with b and so on.

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

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:

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

In that way every division will yield an integer.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文