重复排列:避免溢出 [英] Permutation with Repetition: Avoiding Overflow

问题描述

背景:

给出n个球，使得:

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

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

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

The number of permutations in which these balls can be arranged is given by:

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

问题1: 如何优雅地"计算perm，以便尽可能长时间地避免整数溢出 ，并确保在完成计算后，我要么具有正确的值perm ，或者我知道最终结果将会溢出?

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?

基本上，我想避免使用类似GNU GMP的东西.

Basically, I want to avoid using something like GNU GMP.

(可选)问题2: 这真的不是一个好主意吗?我应该继续使用GMP吗?

Optionally, Question 2: Is this a really bad idea, and should I just go ahead and use GMP?

推荐答案

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

这篇关于重复排列:避免溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！