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)))