Statistiques: combinaisons en Python
j'ai besoin de calculer des combinatoires (nCr) en Python mais je ne trouve pas la fonction pour faire cela dans les bibliothèques math , numpy ou stat . Quelque chose comme une fonction du type:
comb = calculate_combinations(n, r)
j'ai besoin du nombre de combinaisons possibles, pas des combinaisons réelles, donc itertools.combinations ne m'intéresse pas.
enfin, je veux éviter d'utiliser des factoriels, car les nombres que je vais calculer les combinaisons pour peuvent obtenir trop gros et la factorielles sont va être monstrueux.
cela semble comme une question vraiment facile à répondre, mais je me noie dans des questions sur la génération de toutes les combinaisons réelles, qui n'est pas ce que je veux. :)
merci Beaucoup
13 réponses
voir scipy.spécial.PEB (scipy.misc.peigne dans les anciennes versions de scipy). Quand exact est faux, il utilise la fonction gammaln 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.
pourquoi ne pas l'écrire vous-même? C'est une doublure ou un truc du genre:
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) )
essai-impression 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. modifié 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)) donc il ne sera pas err pour grand N /K
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 couples 0 <= (N,k) < 1e3) 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
si vous voulez des résultats exacts et vitesse, essayez gmpy -- gmpy.comb devrait faire exactement ce que vous demandez, et c'est assez rapide (bien sûr, comme gmpy l 'auteur original de l ' am biaisé;-).
si vous voulez un résultat exact, Utilisez sympy.binomial . Ça semble être la méthode la plus rapide, haut les mains.
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
une traduction littérale de la définition mathématique est tout à fait adéquate dans de nombreux cas (en se rappelant que Python utilisera automatiquement l'arithmétique des grands nombres):
from math import factorial
def calculate_combinations(n, r):
return factorial(n) // factorial(r) // factorial(n-r)
pour certaines entrées que j'ai testées (par exemple n=1000 R=500), c'était plus de 10 fois plus rapide que la doublure reduce suggérée dans une autre réponse (actuellement la plus élevée votée). D'un autre côté, il est exécuté par le snippit fourni par @J. F. Sebastian.
Voici une autre alternative. Celui-ci a été écrit à l'origine en C++, donc il peut être rétroporté en C++ pour un entier de précision finie (par exemple __int64). L'avantage est (1) il implique seulement des opérations entières, et (2) il évite de gonfler la valeur entière en faisant des paires successives de multiplication et de division. J'ai testé le résultat avec le triangle Pascal de Nas Banov, il obtient la bonne réponse:
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
raison D'être: minimiser le nombre de multiplications et divisions, nous réécrivons l'expression comme
n! n(n-1)...(n-r+1)
--------- = ----------------
r!(n-r)! r!
pour éviter le débordement de multiplication autant que possible, nous allons évaluer dans l'ordre STRICT suivant, de gauche à droite:
n / 1 * (n-1) / 2 * (n-2) / 3 * ... * (n-r+1) / r
nous pouvons montrer que l'arithmétique entière appliquée dans cet ordre est exacte (c.-à-d. pas d'erreur de arrondi).
en utilisant la programmation dynamique, la complexité temporelle est Θ (N*m) et la complexité spatiale Θ (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]
si votre programme a une limite supérieure à n (dire n <= N ) et a besoin de calculer à plusieurs reprises nCr (de préférence pour > > N fois), en utilisant lru_cache peut vous donner un énorme coup de pouce 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)
construire le cache (ce qui est fait implicitement) prend jusqu'à O(N^2) temps. Tous les appels subséquents à nCr retourneront dans O(1) .
la formule directe produit de grands nombres entiers quand n est plus grand que 20.
donc, encore une autre réponse:
from math import factorial
binomial = lambda n,r: reduce(long.__mul__, range(n-r, n+1), 1L) // factorial(r)
court, rapide et efficace.
c'est assez facile avec sympy.
import sympy
comb = sympy.binomial(n, r)
c'est probablement aussi rapide que vous pouvez le faire en python pur pour des entrées raisonnablement 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
utilisant seulement bibliothèque standard distribuée avec Python :
import itertools
def nCk(n, k):
return len(list(itertools.combinations(range(n), k)))