Statistiques: combinaisons en Python

J'ai besoin de calculer combinatorials (rcn) en Python mais ne trouve pas la fonction pour le faire dans math, numpy ou stat 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.combinations ne m'intéresse pas.

Enfin, je veux l'éviter à l'aide de factorielles, comme les chiffres, je vais être de calculer les combinaisons peuvent être trop 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.

InformationsquelleAutor Morlock | 2010-06-11
  1. 115

    Voir scipy.spécial.peigne (scipy.misc.peigne dans les anciennes versions de scipy). Lorsque exact est Faux, il utilise le gammaln fonction pour obtenir une bonne précision sans prendre beaucoup de temps. Dans le cas précis, il renvoie une précision arbitraire entier, ce qui peut prendre beaucoup de temps à calculer.

    • scipy.misc.comb est dépréciée en faveur de scipy.special.comb depuis la version 0.10.0.
    InformationsquelleAutor Jouni K. Seppänen
  2. 112

    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

    • +1 pour suggérer à écrire quelque chose de simple, pour l'utilisation de la réduire, et pour la fraîcheur de la démo avec le triangle de pascal
    • les points de bonus si vous remplacez range( ..) avec xrange( ... ) en python 2.x 😉
    • Je pense que l'affiche a été la recherche d'une solution plus efficace, adaptée aux grandes entrées (de sorte que l'utilisation d'une boucle for, esp. avec la gamme, serait pas de travail)
    • -1 parce que cette réponse est fausse: imprimer factorielle(54)/(factorielle(54 - 27))/factorial(27) == nCk(54, 27) donne de Faux.
    • Ok, vous avez à la fois la petite et techniquement correcte. Ce que j'ai fait a été conçu comme illustration de la façon d'écrire une fonction; je savais que c'est pas précise pour assez grand N et K en raison de précision en virgule flottante. Mais nous pouvons résoudre ce problème - voir ci-dessus, maintenant il ne devrait pas tre pour de grands nombres
    • J'ai changé de -1 à +1 (Même si je pense que la Fraction peut-être exagéré lol). Je pense juste que c'est bon pour les gens à connaître les limites de fonctions qu'ils utilisent. Cette réponse figure en bonne position sur google recherche de sorte que beaucoup de nouveaux arrivants peuvent utiliser ce code.
    • Ce serait probablement rapide en Haskell, mais pas Python malheureusement. C'est en fait assez lent par rapport à de nombreux autres réponses, par exemple @Alex Martelli, J. F. Sebastian, et de mon propre.
    • Pour Python 3, j'ai dû également from functools import reduce.
    • Je ne pense pas que c'est une bonne idée d'écrire votre propre version de bibliothèque de fonctions, sauf pour le fun 🙂
    • Certaines optimisations peuvent être fait. k = min(k, n - k), comme nCk = nC(n-k), et au lieu de faire un générateur d'expression divisant à chaque fois, de faire toutes les choses que vous avez besoin de multiplier les / toutes les choses que vous avez besoin de diviser. Donc: def nCk(n, k): k = min(k, n - k); dividend = reduce(mul, xrange(n - k + 1, n + 1), 1); divisor = reduce(mul, xrange(1, r + 1), 1); return dividend // divisor
    • il ressemble à la formule de le premier exemple de code dans ma réponse.

    InformationsquelleAutor Nas Banov
  3. 50

    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 les 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
    InformationsquelleAutor jfs
  4. 41

    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, comme gmpys'auteur original, je suis biaisé;-).

    • En effet, gmpy2.comb() est 10 fois plus rapide que choose() de ma réponse pour le code: for k, n in itertools.combinations(range(1000), 2): f(n,k) où f() est soit gmpy2.comb() ou choose() sur Python 3.
    • Puisque vous êtes l'auteur de l'emballage, je vous laisse vous corrigé le lien brisé de sorte qu'il pointe vers le bon endroit....
    • le lien pour code.google.com est un bon endroit (même si le site est dans les archives de mode maintenant). Bien sûr, à partir de là il est facile de trouver le github de l'emplacement, github.com/aleaxit/gmpy , et la PyPI un, pypi.python.org/pypi/gmpy2 , car elle est reliée à la fois!-)
    • Désolé pour la confusion. La page affiche une erreur 404 si le javascript a été (sélectivement) désactivé. Je suppose que c'est pour décourager les voyous AIs de l'incorporation de archivé Google Code du Projet sources tout à fait si facilement?
    InformationsquelleAutor Alex Martelli
  5. 28

    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
    InformationsquelleAutor Jim Garrison
  6. 21

    Une traduction littérale de la définition mathématique est tout à fait adéquat dans beaucoup de cas (en se souvenant que Python utilise automatiquement grand nombre arithmétique):

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

    Pour certains intrants j'ai testé (par exemple n=1000 r=500), c'est plus de 10 fois plus rapide que l'un liner reduce suggéré dans un autre (plus haut voté) réponse. D'autre part, il est réalisé par le snippit fournis par @J. F. Sebastian.

    InformationsquelleAutor Todd Owen
  7. 10

    Voici une autre alternative. Ce fut à l'origine écrit en C++, de sorte qu'il peut être reporté sur C++ pour une durée de précision de type entier (par exemple __int64). L'avantage, c'est (1) elle porte uniquement sur les opérations sur entiers, et (2) il évite les ballonnements la valeur de l'entier en faisant des paires successives de la multiplication et de la division. J'ai testé le résultat avec Nas Banov du triangle de Pascal, il obtient la réponse correcte:

    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

    Justification: afin De minimiser le nombre de multiplications et de divisions, nous réécrire l'expression comme

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

    Pour éviter la multiplication de débordement autant que possible, nous allons évaluer en suivant strictement l'ordre, de gauche à droite:

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

    Nous pouvons montrer que l'entier arithmatic utilisé dans ce type de commande est exacte (pas d'erreur d'arrondi).

    InformationsquelleAutor Wirawan Purwanto
  8. 6

    Utilisant la programmation dynamique, la complexité du temps est en Θ(n*m) et de la complexité de l'espace Θ(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]
    InformationsquelleAutor pantelis300
  9. 4

    Si votre programme a une limite supérieure de n (dire n <= N) et les besoins à plusieurs reprises de calcul de la rcn (préférence pour >>N fois), à l'aide de lru_cache peut vous donner un énorme gain de performance:

    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)

    De la construction de la mémoire cache (ce qui est fait implicitement) prend jusqu'à O(N^2) temps. Les appels suivants à nCr sera de retour dans O(1).

    InformationsquelleAutor yzn-pku
  10. 4

    Vous pouvez écrire 2 fonctions simples qui en fait s'avère être d'environ 5-8X plus rapide que l'utilisation scipy.spécial.peigne. En fait, vous n'avez pas besoin d'importer tous les paquets supplémentaires, et la fonction est tout à fait lisible. L'astuce est d'utiliser memoization pour stocker les valeurs précédemment calculées, et en utilisant la définition de rcn

    # create a memoization dict
memo = {}
def factorial(n):
"""
Calculate the factorial of an input using memoization
:param n: int
:rtype value: int
"""
if n in [1,0]:
return 1
if n in memo:
return memo[n]
value = n*fact(n-1)
memo[n] = value
return value
def ncr(n, k):
"""
Choose k elements from a set of n elements - n must be larger than or equal to k
:param n: int
:param k: int
:rtype: int
"""
return factorial(n)/(factorial(k)*factorial(n-k))

    Si nous comparons les temps de

    from scipy.special import comb
%timeit comb(100,48)
>>> 100000 loops, best of 3: 6.78 µs per loop
%timeit ncr(100,48)
>>> 1000000 loops, best of 3: 1.39 µs per loop
    • Ces jours-ci, il y a un memoize décorateur dans functools appelé lru_cache qui peut simplifier votre code?
    InformationsquelleAutor PyRsquared
  11. 3

    De départ Python 3.8, de la bibliothèque standard comprend maintenant la math.peigne fonction pour calculer le coefficient binomial:

    mathématiques.comb(n, k)

    qui est le nombre de façons de choisir k objets parmi n objets sans répétition
    n! /(k! (n - k)!):

    import math
math.comb(10, 5) # 252
    InformationsquelleAutor Xavier Guihot
  12. 2

    C'est assez facile avec sympy.

    import sympy
comb = sympy.binomial(n, r)
    InformationsquelleAutor Bobby
  13. 2

    En utilisant uniquement de la bibliothèque standard distribué avec Python:

    import itertools
def nCk(n, k):
return len(list(itertools.combinations(range(n), k)))
    • je ne pense pas que son temps de la complexité (et l'utilisation de la mémoire) est acceptable.
    InformationsquelleAutor MarianD
  14. 2

    Directe de la formule produit des grands entiers si n est plus grand que 20.

    Donc, encore une autre réponse:

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

    court, précis et efficace, car cela évite de python grands entiers en collant avec la nostalgie.

    Il est plus précis et plus rapide lors de la comparaison de scipy.spécial.peigne:

     >>> from scipy.special import comb
>>> nCr = lambda n,r: reduce(long.__mul__, range(n-r+1, n+1), 1L) // factorial(r)
>>> comb(128,20)
1.1965669823265365e+23
>>> nCr(128,20)
119656698232656998274400L  # accurate, no loss
>>> from timeit import timeit
>>> timeit(lambda: comb(n,r))
8.231969118118286
>>> timeit(lambda: nCr(128, 20))
3.885951042175293
    • C'est une erreur! Si n == r, le résultat devrait être de 1. Ce code renvoie 0.
    • Plus précisément, il convient de range(n-r+1, n+1) au lieu de range(n-r,n+1).
    InformationsquelleAutor olivecoder
  15. 1

    C'est @killerT2333 code à l'aide de la builtin memoization décorateur.

    from functools import lru_cache
@lru_cache()
def factorial(n):
"""
Calculate the factorial of an input using memoization
:param n: int
:rtype value: int
"""
return 1 if n in (1, 0) else n * factorial(n-1)
@lru_cache()
def ncr(n, k):
"""
Choose k elements from a set of n elements,
n must be greater than or equal to k.
:param n: int
:param k: int
:rtype: int
"""
return factorial(n) / (factorial(k) * factorial(n - k))
print(ncr(6, 3))
    InformationsquelleAutor demented hedgehog
  16. 0

    C'est probablement aussi vite que vous pouvez le faire en pure python pour raisonnablement grandes entrées:

    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
    InformationsquelleAutor Rabih Kodeih
  17. 0

    Cette fonction est très optimazed.

    def nCk(n,k):
m=0
if k==0:
m=1
if k==1:
m=n
if k>=2:
num,dem,op1,op2=1,1,k,n
while(op1>=1):
num*=op2
dem*=op1
op1-=1
op2-=1
m=num//dem
return m
    InformationsquelleAutor Santiago Coca Rojas
  18. 0

    Ici est un algorithme efficace pour vous

    for i = 1.....r
p = p * ( n - i ) / i
print(p)

    Par exemple rcn(30,7)
    = fact(30) /( fait(7) * fact(23))
    = ( 30 * 29 * 28 * 27 * 26 * 25 * 24 ) /(1 * 2 * 3 * 4 * 5 * 6 * 7)

    Donc, il suffit d'exécuter la boucle de 1 à r peut obtenir le résultat.

    InformationsquelleAutor kta