[Résolu] Algo calcul nombre de combinaisons

[Persalteas]

Salut,

Vous connaissez peut être la formule du nombre de combinaisons:
Si je veux calculer les nombre de façons de tirer 3 éléments dans 10 éléments, je fais:

$mathjax$\bigl(\begin{smallmatrix}
10\\
3
\end{smallmatrix}\bigr) = \frac{10!}{3! (10-3)!}$mathjax$

Bon, il se trouve que j'ai besoin non pas 10 éléments mais de 1000.
On a tous remarqué que les calculatrices ne dépassent pas le calcul de 69! (70! dépasse 10^100), et pourtant, les TI et Casio sont capables de retourner sans problème le nombre de combinaisons dans 1000 éléments, alors qu'il me semblait avoir besoin d'utiliser un 1000! ...

J'imagine donc qu'en mémoire, elle repère direct le

$mathjax$\frac{1000!}{ (997)!}$mathjax$

et donc ne calcule que 1000*999*998.
Est-ce que vous connaissez plus en détail avec quel algo ce calcul est réalisé ?

[Bisam]

Euh, ben, c'est facile, il suffit de ne pas utiliser cette formule avec les factorielles... parce qu'elle est pourrie au niveau de la complexité algorithmique.

Le mieux est de remarquer que

$mathjax$\displaystyle \binom{n}{p}=\frac{1}{p!}\prod_{k=n-p+1}^{n}k$mathjax$

.
On est ramené à effectuer

$mathjax$2p$mathjax$

produits et 1 division à la fin.
On peut encore diminuer le nombre de calculs en remarquant que

$mathjax$\binom{n}{p}=\binom{n}{n-p}$mathjax$

et en choisissant la plus petite des 2 valeurs entre

$mathjax$p$mathjax$

et

$mathjax$n-p$mathjax$

.

On peut alors faire le calcul ainsi :

Code: Tout sélectionner

def binom(n, p):
    """Renvoie le coefficient binomial C(n,p)"""
    num = denom = 1
    if p > n-p:
        p = n-p
    for i in range(1, p+1):
        num *= n-i+1
        denom *= i
    return num // denom

[Persalteas]

C'est parfait !

Merci beaucoup !