programa - permutaciones python 3

Estadísticas: combinaciones en Python

Question

Necesito calcular combinatorials (nCr) en Python pero no puedo encontrar la función para hacer eso en las bibliotecas math , numpy o stat . Algo así como una función del tipo:

comb = calculate_combinations(n, r)

Necesito el número de combinaciones posibles, no las combinaciones reales, por lo que itertools.combinations no me interesa.

Finalmente, quiero evitar el uso de factoriales, ya que los números que voy a calcular para las combinaciones pueden ser demasiado grandes y los factoriales van a ser monstruosos.

Esto parece una pregunta REALMENTE fácil de responder, sin embargo, estoy ahogado en preguntas sobre la generación de todas las combinaciones reales, que no es lo que quiero. :)

Muchas gracias

Answer 1

¿Por qué no escribirlo usted mismo? Es un trazador de líneas o tal:

from operator import mul # or mul=lambda x,y:x*y
from fractions import Fraction
def nCk(n,k):
return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )

Prueba - impresión del triángulo de Pascal:

>>> for n in range(17):
... print '' ''.join(''%5d''%nCk(n,k) for k in range(n+1)).center(100)
...
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
>>>

PD. editado para reemplazar int(round(reduce(mul, (float(ni)/(i+1) for i in range(k)), 1))) con int(reduce(mul, (Fraction(ni, i+1) for i in range(k)), 1)) por lo que no se equivocará para N / K grande

Answer 2

Aquí hay otra alternativa. Este fue escrito originalmente en C ++, por lo que se puede backported a C ++ para un entero de precisión finita (por ejemplo, __int64). La ventaja es (1) solo involucra operaciones enteras, y (2) evita hinchar el valor entero haciendo pares sucesivos de multiplicación y división. Probé el resultado con el triángulo de Pascal de Nas Banov, obtuvo la respuesta correcta:

def choose(n,r):
"""Computes n! / (r! (n-r)!) exactly. Returns a python long int."""
assert n >= 0
assert 0 <= r <= n
c = 1L
denom = 1
for (num,denom) in zip(xrange(n,n-r,-1), xrange(1,r+1,1)):
c = (c * num) // denom
return c

Justificación: para minimizar el número de multiplicaciones y divisiones, reescribimos la expresión como

 n! n(n-1)...(n-r+1)
--------- = ----------------
r!(n-r)! r!

Para evitar el desbordamiento de la multiplicación tanto como sea posible, lo evaluaremos en el siguiente orden ESTRICTO, de izquierda a derecha:

n / 1 * (n-1) / 2 * (n-2) / 3 * ... * (n-r+1) / r

Podemos demostrar que el entero aritmático operado en este orden es exacto (es decir, no hay error de redondeo).

Answer 3

Consulte scipy.special.comb (scipy.misc.comb en versiones anteriores de scipy). Cuando exact es False, utiliza la función gammaln para obtener una buena precisión sin tomar demasiado tiempo. En el caso exacto, devuelve un entero de precisión arbitraria, que puede tardar mucho tiempo en computarse.

Answer 4

Es bastante fácil con Sympy.

import sympy
comb = sympy.binomial(n, r)

Answer 5

Eso es probablemente tan rápido como lo puedes hacer en python puro para entradas razonablemente grandes:

def choose(n, k):
if k == n: return 1
if k > n: return 0
d, q = max(k, n-k), min(k, n-k)
num = 1
for n in xrange(d+1, n+1): num *= n
denom = 1
for d in xrange(1, q+1): denom *= d
return num / denom

Answer 6

La fórmula directa produce números enteros grandes cuando n es mayor que 20.

Entonces, otra respuesta más:

from math import factorial
binomial = lambda n,r: reduce(long.__mul__, range(n-r, n+1), 1L) // factorial(r)

corto, rápido y eficiente.

Answer 7

Si quiere un resultado exacto, use sympy.binomial . Parece ser el método más rápido, sin dudas.

x = 1000000
y = 234050
%timeit scipy.misc.comb(x, y, exact=True)
1 loops, best of 3: 1min 27s per loop
%timeit gmpy.comb(x, y)
1 loops, best of 3: 1.97 s per loop
%timeit int(sympy.binomial(x, y))
100000 loops, best of 3: 5.06 µs per loop

Answer 8

Si quieres resultados exactos y velocidad, prueba gmpy - gmpy.comb debería hacer exactamente lo que pides, y es bastante rápido (por supuesto, como autor original de gmpy , estoy predispuesto ;-).

Answer 9

Si su programa tiene un límite superior a n (digamos n <= N ) y necesita calcular nCr (preferiblemente por >> N veces), el uso de lru_cache puede darle un gran aumento de rendimiento:

from functools import lru_cache
@lru_cache(maxsize=None)
def nCr(n, r):
return 1 if r == 0 or r == n else nCr(n - 1, r - 1) + nCr(n - 1, r)

La construcción de la memoria caché (que se realiza implícitamente) lleva hasta O(N^2) tiempo. Cualquier llamada subsiguiente a nCr volverá en O(1) .

Answer 10

Una búsqueda rápida en el código de google da (usa la fórmula de la respuesta de @Mark Byers ):

def choose(n, k):
"""
A fast way to calculate binomial coefficients by Andrew Dalke (contrib).
"""
if 0 <= k <= n:
ntok = 1
ktok = 1
for t in xrange(1, min(k, n - k) + 1):
ntok *= n
ktok *= t
n -= 1
return ntok // ktok
else:
return 0

choose() es 10 veces más rápido (probado en todos los 0 <= (n, k) <1e3 pares) que scipy.misc.comb() si necesita una respuesta exacta.

def comb(N,k): # from scipy.comb(), but MODIFIED!
if (k > N) or (N < 0) or (k < 0):
return 0L
N,k = map(long,(N,k))
top = N
val = 1L
while (top > (N-k)):
val *= top
top -= 1
n = 1L
while (n < k+1L):
val /= n
n += 1
return val

Answer 11

Una traducción literal de la definición matemática es bastante adecuada en muchos casos (recordando que Python utilizará automáticamente la aritmética de números grandes):

from math import factorial
def calculate_combinations(n, r):
return factorial(n) // factorial(r) // factorial(n-r)

Para algunas entradas que probé (p. Ej., N = 1000 r = 500), esto fue más de 10 veces más rápido que la reduce trazador de líneas sugerida en otra respuesta (actualmente el más votado). Por otro lado, está superado por el snippit provisto por @JF Sebastian.

Answer 12

Usando la programación dinámica, la complejidad del tiempo es Θ (n * m) y la complejidad del espacio Θ (m):

def binomial(n, k):
""" (int, int) -> int
| c(n-1, k-1) + c(n-1, k), if 0 < k < n
c(n,k) = | 1 , if n = k
| 1 , if k = 0
Precondition: n > k
>>> binomial(9, 2)
36
"""
c = [0] * (n + 1)
c[0] = 1
for i in range(1, n + 1):
c[i] = 1
j = i - 1
while j > 0:
c[j] += c[j - 1]
j -= 1
return c[k]

Answer 13

Usando solo la biblioteca estándar distribuida con Python :

import itertools
def nCk(n, k):
return len(list(itertools.combinations(range(n), k)))