Contando combinaciones y permutaciones eficientemente.

Tengo un código para contar permutaciones y combinaciones, y estoy tratando de hacer que funcione mejor para grandes números.

He encontrado un mejor algoritmo para permutaciones que evita grandes resultados intermedios, pero aún creo que puedo hacerlo mejor para las combinaciones.

Hasta ahora, he puesto un caso especial para reflejar la simetría de nCr, pero todavía me gustaría encontrar un mejor algoritmo que evite la llamada a factorial (r), que es un resultado intermedio innecesariamente grande. Sin esta optimización, la última prueba lleva demasiado tiempo tratando de calcular factorial (99000).

¿Alguien puede sugerir una forma más eficiente de contar combinaciones?

from math import factorial def product(iterable): prod = 1 for n in iterable: prod *= n return prod def npr(n, r): """ Calculate the number of ordered permutations of r items taken from a population of size n. >>> npr(3, 2) 6 >>> npr(100, 20) 1303995018204712451095685346159820800000 """ assert 0 <= r >> ncr(3, 2) 3 >>> ncr(100, 20) 535983370403809682970 >>> ncr(100000, 1000) == ncr(100000, 99000) True """ assert 0 <= r  n // 2: r = n - r return npr(n, r) // factorial(r) 

si n no está lejos de r, entonces es mejor utilizar la definición recursiva de combinación, ya que xC0 == 1 solo tendrá algunas iteraciones:

La definición recursiva relevante aquí es:

nCr = (n-1) C (r-1) * n / r

Esto se puede calcular bien usando la recursión de la cola con la siguiente lista:

[(n – r, 0), (n – r + 1, 1), (n – r + 2, 2), …, (n – 1, r – 1), (n, r)]

que, por supuesto, se genera fácilmente en Python (omitimos la primera entrada desde nC0 = 1) por izip(xrange(n - r + 1, n+1), xrange(1, r+1)) Tenga en cuenta que esto supone que r < = n necesitas verificar eso e intercambiarlos si no lo están. También para optimizar el uso si r

Ahora simplemente necesitamos aplicar el paso de recursión usando la recursión de la cola con reducir. Comenzamos con 1 porque nC0 es 1 y luego multiplicamos el valor actual con la siguiente entrada de la lista como se muestra a continuación.

 from itertools import izip reduce(lambda x, y: x * y[0] / y[1], izip(xrange(n - r + 1, n+1), xrange(1, r+1)), 1) 

Dos sugerencias bastante simples:

  1. Para evitar el desbordamiento, hacer todo en el espacio de registro. Utilice el hecho de que log (a * b) = log (a) + log (b), y log (a / b) = log (a) – log (b). Esto facilita el trabajo con factoriales muy grandes: log (n! / M!) = Log (n!) – log (m!), Etc.

  2. Usa la función gamma en lugar de factorial. Puedes encontrar uno en scipy.stats.loggamma . Es una forma mucho más eficiente de calcular log-factorials que la sum directa. loggamma(n) == log(factorial(n - 1)) , y de manera similar, gamma(n) == factorial(n - 1) .

Si no necesita una solución de python puro, gmpy2 podría ayudar ( gmpy2.comb es muy rápido).

Hay una función para esto en scipy que aún no se ha mencionado: scipy.special.comb . Parece eficiente en función de algunos resultados de tiempo rápidos para su doctest (~ 0.004 segundos para el comb(100000, 1000, 1) == comb(100000, 99000, 1) ).

[Si bien esta pregunta específica parece ser sobre algoritmos, la pregunta es si una función ncr matemática en python está marcada como un duplicado de esto …]

Si su problema no requiere conocer el número exacto de permutaciones o combinaciones, entonces podría usar la aproximación de Stirling para el factorial.

Eso llevaría a un código como este:

 import math def stirling(n): # http://en.wikipedia.org/wiki/Stirling%27s_approximation return math.sqrt(2*math.pi*n)*(n/math.e)**n def npr(n,r): return (stirling(n)/stirling(nr) if n>20 else math.factorial(n)/math.factorial(nr)) def ncr(n,r): return (stirling(n)/stirling(r)/stirling(nr) if n>20 else math.factorial(n)/math.factorial(r)/math.factorial(nr)) print(npr(3,2)) # 6 print(npr(100,20)) # 1.30426670868e+39 print(ncr(3,2)) # 3 print(ncr(100,20)) # 5.38333246453e+20 

Si está calculando N, elija K (que es lo que creo que está haciendo con ncr), existe una solución de progtwigción dinámica que puede ser mucho más rápida. Esto evitará el factorial, además puede mantener la tabla si lo desea para su uso posterior.

Aquí hay un enlace de enseñanza para ello:

http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html

Sin embargo, no estoy seguro de cómo resolver mejor su primer problema, lo siento.

Edición: Aquí está la maqueta. Hay algunos errores bastante divertidos de uno en uno, por lo que sin duda puede aguantar un poco más de limpieza.

 import sys n = int(sys.argv[1])+2#100 k = int(sys.argv[2])+1#20 table = [[0]*(n+2)]*(n+2) for i in range(1,n): table[i][i] = 1 for i in range(1,n): for j in range(1,ni): x = i+j if j == 1: table[x][j] = 1 else: table[x][j] = table[x-1][j-1] + table[x-1][j] print table[n][k] 
 from scipy import misc misc.comb(n, k) 

debería permitirte contar combinaciones

Solución más eficiente para nCr: espacio y precisión.

Se garantiza que el intermediario (res) siempre será int y nunca mayor que el resultado. La complejidad del espacio es O (1) (sin listas, sin cremalleras, sin stack), la complejidad del tiempo es O (r): exactamente r multiplicaciones y r divisiones.

 def ncr(n, r): r = min(r, nr) if r == 0: return 1 res = 1 for k in range(1,r+1): res = res*(n-k+1)/k return res 
 from numpy import prod def nCr(n,r): numerator = range(n, max(nr,r),-1) denominator = range(1, min(nr,r) +1,1) return int(prod(numerator)/prod(denominator)) 

El uso de xrange() lugar de range() acelerará un poco las cosas debido a que no se crea, rellena, itera y se destruye una lista intermedia. Además, reduce() con operator.mul .

Para N elegir K puedes usar el triángulo de Pascales. Básicamente, necesitarías mantener una matriz de tamaño N alrededor para calcular todos los N valores K selectos. Sólo se requerirán adiciones.

Podría ingresar dos enteros e importar la biblioteca matemática para encontrar el factorial y luego aplicar la fórmula nCr

 import math n,r=[int(_)for _ in raw_input().split()] f=math.factorial print f(n)/f(r)/f(nr)