重复排列：避免溢出问题

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吗？

- ArjunShankar

---

为什么你要避免使用GMP？通常，你想尽可能少地工作。 - Dave

检测溢出实际上是C语言的一个弱点。假设你尽可能地避免溢出，因此可以确信只有在没有溢出的情况下才能计算出正确的值。即便如此，你仍然无法确定是否真的发生了溢出。 - ruakh

@Dave：你说得没错。但问题仍然很有趣。所以对于那些更关心“如何”而不是“为什么”的人来说，问题仍然存在 :）。也许有人最终会在交互式烤面包机中使用它：P - ArjunShankar

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

然后，使用递归计算系数就变得简单了。请注意，为了避免指数时间复杂度，您需要缓存结果（避免重新计算）或使用动态规划。

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

是的，使用任意精度库完成这个简单任务是非常糟糕的想法。

- tskuzzy

---

有道理。不过肯定需要一些动态规划 :-) - ruakh

是的，记忆化是必须的 :) - tskuzzy

Answer 2

如果你有大量的CPU时间，可以将所有阶乘制成列表，然后找到列表中所有数字的质因数分解，然后将分子分母上的公共因子约掉，直到数字完全简化。

- Dave

---

你预计 N 会变得有多大？ - Dave

N代表编译器后端正在优化的“基本块”中指令的数量。因此，如果有人编写了一堆没有控制语句的代码[但仍然是整数]，那么N可能会非常大。这种算法可能对我的一个同事很有用，他正在为一个晦涩的DSP架构实现一个晦涩的优化传递。避免使用GMP更多地是一种心血来潮，而不是要求。 - ArjunShankar

对于这个问题，这个算法已经足够快了。然而，在我看来，编写一个因数分解和约分算法所花费的时间有些过度了。 - tskuzzy

同意。我现在标记为正确，因为这是一个干净、我认为优雅的解决方案。 - ArjunShankar

Answer 3

最安全的溢出方式是Dave建议的方式。您可以通过以下求和公式找到质数p除以n!的指数：

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

减去在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+部件数量-1次乘法，保持中间结果适度小。

- Daniel Fischer

Answer 4

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

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

- Evgeny Kluev

Answer 5

注释：n！= prod（1，n）其中prod你可以猜测它的含义。

这很容易，但首先您必须知道对于任何两个正整数（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

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

- Mihai Manole