Statistiques: combinaisons en Python

Question

J'ai besoin de calculer combinatorials (rcn) en Python mais ne trouve pas la fonction pour le faire dans les "mathématiques", 'numyp' ou 'stat' des bibliothèques. Quelque chose comme une fonction du type:

comb = calculate_combinations(n, r)

J'ai besoin de connaître le nombre de combinaisons possibles, et pas les combinaisons, ce qui itertools.les combinaisons ne m'intéresse pas.

Enfin, je veux l'éviter à l'aide de factorielles, comme les chiffres, je vais être de calculer les combinaisons pour pouvez obtenir de gros et les factorielles sont va être monstrueux.

Cela semble VRAIMENT facile de répondre à la question, mais je suis d'être noyé dans des questions à propos de générer toutes les combinaisons, ce qui n'est pas ce que je veux. :)

Merci beaucoup

Answer 1

Voir scipy.misc.le peigne. À moins que des réponses exactes sont demandés, il utilise le gammaln fonction pour obtenir une bonne précision sans prendre beaucoup de temps. Dans le cas précis, il renvoie un Python de long, ce qui peut prendre longtemps à calculer.

Answer 2

Pourquoi ne pas écrire vous-même? C'est un one-liner ou tel:

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

Test d'impression le triangle 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
>>> 

PS. édité pour remplacer int(round(reduce(mul, (float(n-i)/(i+1) for i in range(k)), 1))) avec int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1)) afin de ne pas tre pour big N/K

Answer 3

Une recherche rapide sur google code donne (il utilise la formule de @Mark Byers réponse):

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() est 10 fois plus rapide (testé sur tous 0 <= (n,k) < 1e3 paires) que scipy.misc.comb() si vous avez besoin d'une réponse exacte.

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 4

Si vous voulez des résultats exacts et vitesse, essayez de gmpy -- gmpy.comb faire exactement ce que vous demandez, et il est assez rapide (bien sûr, gmpys'auteur original, je suis partial;-).

Answer 5

Si vous voulez un résultat exact, utilisez sympy.binomial. Il semble être la méthode la plus rapide, les mains vers le bas.

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