python - programa - contar combinaciones y permutaciones de manera eficiente
permutaciones python 3 (11)
Tengo un código para contar permutaciones y combinaciones, y estoy tratando de hacerlo funcionar mejor para números grandes.
He encontrado un algoritmo mejor para las permutaciones que evita grandes resultados intermedios, pero todavía creo que puedo mejorar las combinaciones.
Hasta ahora, he presentado un caso especial para reflejar la simetría de nCr, pero aún me gustaría encontrar un algoritmo mejor que evite la llamada a factorial (r), que es un resultado intermedio innecesariamente grande. Sin esta optimización, el último doctest tarda demasiado tiempo en calcular factorial (99000).
¿Alguien puede sugerir una manera 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 <= n
return product(range(n - r + 1, n + 1))
def ncr(n, r):
"""
Calculate the number of unordered combinations of r items taken from a
population of size n.
>>> ncr(3, 2)
3
>>> ncr(100, 20)
535983370403809682970
>>> ncr(100000, 1000) == ncr(100000, 99000)
True
"""
assert 0 <= r <= n
if r > n // 2:
r = n - r
return npr(n, r) // factorial(r)
Dos sugerencias bastante simples:
Para evitar el desbordamiento, haga todo lo que esté en el espacio de registro. Use el hecho de que log (a * b) = log (a) + log (b) y log (a / b) = log (a) - log (b). Esto hace que sea fácil trabajar con factoriales muy grandes: log (n! / M!) = Log (n!) - log (m!), Etc.
Use la función gamma en lugar de factorial. Puede encontrar uno en
scipy.stats.loggamma. Es una forma mucho más eficiente de calcular los logaritmos que la suma directa.loggamma(n) == log(factorial(n - 1)), y de manera similar,gamma(n) == factorial(n - 1).
El uso de xrange() lugar de range() acelerará ligeramente las cosas debido al hecho de que no se crea, llena, itera y destruye ninguna lista intermedia. Además, reduce() con operator.mul .
Hay una función para esto en scipy que no se ha mencionado aún: scipy.special.comb . Parece eficiente en función de algunos resultados rápidos de tiempo para su doctest (~ 0.004 segundos para comb(100000, 1000, 1) == comb(100000, 99000, 1) ).
[Si bien esta pregunta específica parece ser acerca de los algoritmos, la pregunta es si hay una función math ncr en python marcada como un duplicado de esto ...]
Para N elige K podrías usar el triángulo Pascals. Básicamente, necesitaría mantener una matriz de tamaño N alrededor para calcular todos los N valores de K seleccionados. Solo se requerirán adiciones.
Puede 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(n-r)
Si está computando N, elija K (que es lo que creo que está haciendo con ncr), existe una solución de programación dinámica que puede ser mucho más rápida. Esto evitará factorial, además puedes guardar la tabla si quieres para un 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.
Editar: Aquí está la maqueta. Hay algunos errores muy hilarantes, por lo que ciertamente puede soportar 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,n-i):
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]
Si no necesita una solución de python puro, gmpy2 podría ayudar ( gmpy2.comb es muy rápido).
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(n-r) if n>20 else
math.factorial(n)/math.factorial(n-r))
def ncr(n,r):
return (stirling(n)/stirling(r)/stirling(n-r) if n>20 else
math.factorial(n)/math.factorial(r)/math.factorial(n-r))
print(npr(3,2))
# 6
print(npr(100,20))
# 1.30426670868e+39
print(ncr(3,2))
# 3
print(ncr(100,20))
# 5.38333246453e+20
Solución más eficiente para nCr: espacio sabio y precisión sabia.
El intermediario (res) garantiza que siempre será int y nunca mayor que el resultado. La complejidad del espacio es O (1) (sin listas, sin cremalleras, sin pila), la complejidad del tiempo es O (r) - exactamente r multiplicaciones y r divisiones.
def ncr(n, r):
r = min(r, n-r)
if r == 0: return 1
res = 1
for k in range(1,r+1):
res = res*(n-k+1)/k
return res
si n no está lejos de r, entonces usar la definición recursiva de combinación es probablemente mejor, 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 muy bien utilizando recursividad de 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 necesita verificar eso e intercambiarlos si no lo están. También para optimizar el uso si r <n / 2 luego r = n - r.
Ahora simplemente tenemos que aplicar el paso de recursión utilizando recursión de cola con reducir. Comenzamos con 1 ya que 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)
from scipy import misc
misc.comb(n, k)
debería permitirle contar combinaciones