Permutación con Repetición: desbordamiento Evitar

Question

Antecedentes:

Dada n bolas tal que:

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

(por supuesto a + b + c + ... = n)

se le da el número de permutaciones en el que estas bolas se pueden organizar por:

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

Pregunta 1: Como puedo 'elegante' calcular perm a fin de evitar un desbordamiento de enteros como el mayor tiempo posible, y estar seguros de que cuando haya terminado el cálculo, yo tampoco tengo el valor correcto de perm, o yo sé que la el resultado final se desbordará?

Básicamente, quiero evitar usar algo como GNU GMP.

Opcionalmente, Pregunta 2: ¿Es esta una mala idea realmente, y debería seguir adelante y usar GMP?

Answer 1

Si tiene globs de tiempo de CPU, puede hacer listas de todos los factores, luego encontrar la factorización prima de todos los números en la lista, luego cancelar todos los números en la parte superior con los de abajo, hasta los números están completamente reducidos

Answer 2

Estos son conocidos como los coeficientes multinomiales, que denotaré por m(a,b,...).

Y se puede calcular de manera eficiente evitando el desbordamiento mediante la explotación de esta identidad (que debería ser bastante fácil de probar):

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 

entonces es una simple cuestión de utilizar la recursividad para el cálculo de los coeficientes. Tenga en cuenta que para evitar un tiempo de ejecución exponencial, necesita almacenar en caché sus resultados (para evitar el recálculo) o usar programación dinámica.

Para comprobar el desbordamiento, solo asegúrese de que las sumas no se desborden.

Y sí, es una muy mala idea usar bibliotecas de precisión arbitrarias para hacer esta simple tarea.

Answer 3

La manera más segura del desbordamiento es la que sugirió Dave. Puedes encontrar el exponente con el que el primer p divide por la suma n!

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

Resta los exponentes de p en las factorizaciones de a! etc. hacer eso por todos los primos <= n, y usted tiene la factorización del coeficiente multinomial. Ese cálculo se desborda si y solo si el resultado final se desborda. Pero los coeficientes multinomiales crecen bastante rápido, por lo que ya tendrá desbordamiento para una cantidad bastante pequeña de n. Para cálculos sustanciales, necesitará una biblioteca bignum (si no necesita resultados exactos, puede obtener un poco más de tiempo usando double s).

Incluso si utiliza una biblioteca bignum, vale la pena mantener los resultados intermedios de conseguir demasiado grande, así que en vez de calcular los factoriales y dividir números enormes, es mejor para calcular las partes en secuencia,

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

y para calcular cada uno de estos factores, tomemos el segundo modo de ilustración,

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

se calcula con

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

Finalmente multiplique las partes. Esto requiere n divisiones y n + number_of_parts - 1 multiplicaciones, manteniendo los resultados intermedios moderadamente pequeños.

Answer 4

De acuerdo con this link, puede calcular los coeficientes multinomiales como producto de varios coeficientes binomiales, controlando el desbordamiento de enteros en el camino.

Esto reduce el problema original al cálculo controlado por desbordamiento de un coeficiente binomial.

Answer 5

Notaciones: n! = prod(1,n) donde prod puede adivinar lo que hace.

Es muy fácil, pero primero hay que saber que para cualquiera de los 2 números enteros positivos (i, n > 0) esa expresión es un entero positivo:

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

Así, la idea es cortar el cálculo de n! en pequeños trozos y dividir lo antes posible

Con a, que con b y así sucesivamente.

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

Cada uno de estos factores es un entero, por lo que si perm no se desborde, ni uno de sus factores va a hacer.

Sin embargo, en el cálculo de un tal factor podría ser un desbordamiento en el numerador o el denominador pero eso es evitable haciendo una multiplicación en el numerador a continuación, una división en alternancia:

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

De esta manera todas las divisiones producirá una entero.