Permutación con Repetición: Evitando el Desbordamiento

Fondo:

Dadas n bolas tales 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 )

El número de permutaciones en que se pueden organizar estas bolas viene dado por:

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

Pregunta 1: ¿Cómo puedo calcular “con elegancia” la perm para evitar un desbordamiento de enteros el mayor tiempo posible y estar seguro de que cuando termine de calcular, tenga el valor correcto de perm o que el resultado final? se desbordará?

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

Opcionalmente, Pregunta 2: ¿Es realmente una mala idea y debo seguir adelante y usar GMP?

Si tiene globos de tiempo de CPU, puede hacer listas de todos los factoriales, luego encontrar la factorización prima de todos los números en las listas, luego cancelar todos los números en la parte superior con los de la parte inferior, hasta que los números estén completamente reducido.

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

Y puede calcularlos de manera eficiente evitando el desbordamiento explotando esta identidad (que debería ser bastante simple 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 cuestión simple de usar la recursión para calcular los coeficientes. Tenga en cuenta que para evitar un tiempo de ejecución exponencial, debe almacenar en caché los resultados (para evitar recálputos) o utilizar la progtwigción dinámica.

Para verificar el desbordamiento, solo asegúrese de que las sums no se desborden.

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

La manera más segura de rebosar es la forma en que Dave sugirió. ¡Encuentras el exponente con el que el primo p divide n! por la sum

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

Resta los exponentes de p en las factorizaciones de a! Haz eso para todos los números primos <= n , y tendrás 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 habrá desbordado para n bastante pequeño. Para cálculos sustanciales, necesitará una gran biblioteca (si no necesita resultados exactos, puede obtener un poco más de tiempo usando el double s).

Incluso si utiliza una biblioteca bignum, vale la pena evitar que los resultados intermedios se vuelvan demasiado grandes, por lo que en lugar de calcular los factoriales y dividir grandes números, es mejor calcular las partes en secuencia.

 n!/(a! * b! * c! * ...) = n! / (a! * (na)!) * (na)! / (b! * (nab)!) * ... 

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

 (na)! / (b! * (nab)!) = \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 multiplica las partes. Esto requiere n divisiones y n + number_of_parts - 1 multiplicaciones, manteniendo los resultados intermedios moderadamente pequeños.

De acuerdo con este enlace , puede calcular los coeficientes multinomiales como un 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.

Notaciones: n! = prod(1,n) n! = prod(1,n) donde podéis adivinar qué hace.

Es muy fácil, pero primero debe saber que para cualquier entero de 2 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 trozos pequeños 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 número entero, por lo que si el perm no se desbordará, ninguno de sus factores funcionará.

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

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

De esa manera, cada división producirá un entero.