combinatorial - ¿Hay una función math nCr en python?

plot title python

Question

Posibles duplicados:
Estadísticas: combinaciones en Python
contar combinaciones y permutaciones de manera eficiente
Problema del proyecto euler en python (problema 53)

Estoy buscando ver si la biblioteca matemática en python está integrada en la función nCr (n Choose r):

Entiendo que esto se puede programar, pero pensé que verificaría si ya estaba incorporado antes que yo.

Answer 1

¿Quieres iteración? itertools.combinations . Uso común:

>>> import itertools
>>> itertools.combinations(''abcd'',2)
<itertools.combinations object at 0x01348F30>
>>> list(itertools.combinations(''abcd'',2))
[(''a'', ''b''), (''a'', ''c''), (''a'', ''d''), (''b'', ''c''), (''b'', ''d''), (''c'', ''d'')]
>>> [''''.join(x) for x in itertools.combinations(''abcd'',2)]
[''ab'', ''ac'', ''ad'', ''bc'', ''bd'', ''cd'']

Si solo necesita calcular la fórmula, use math.factorial :

import math

def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

if __name__ == ''__main__'':
    print nCr(4,2)

En Python 3, use la división de enteros // lugar de / para evitar desbordamientos:

return f(n) // f(r) // f(nr)

Salida

6

Answer 2

El siguiente programa calcula nCr de una manera eficiente (en comparación con el cálculo de factoriales, etc.)

import operator as op
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, xrange(n, n-r, -1), 1)
    denom = reduce(op.mul, xrange(1, r+1), 1)
    return numer//denom