Faisons un calcul de combinaison avec Python

Sensibilisation aux problèmes

Dans Article précédent, j'ai fait le calcul de combinaison récursivement en Python, mais je pensais qu'il y avait d'autres moyens.

Revue des combinaisons

C'est la combinaison que j'ai apprise dans la combinaison d'ordre

_nC_r=\frac{n!}{r!(n-r)!}

C'était. Ici, quand n <r, la combinaison est 0, c'est-à-dire

_0C_1=0

Je promets «0» s'il est hors de la définition.

Comme une formule progressive

Cette fois, je veux utiliser la méthode d'appel de la fonction récursivement avec Python, donc je vais préparer quelque chose comme une expression graduelle.

Decay 1: Diminuer r

_nC_r=_nC_{r-1}\times\frac{n-r+1}{r}

Preuve

Premièrement, à partir de la définition

_nC_r=\frac{n!}{r!(n-r)!}=\frac{n!}{r\times(r-1)!\times(n-r)!}=\frac{n!}{(r-1)!\times(n-r)!}\times\frac{1}{r}\\
_nC_{r-1}=\frac{n!}{(r-1)!\times(n-r+1)\times(n-r)!}=\frac{n!}{(r-1)!\times(n-r)!}\times\frac{1}{n-r+1}

Donc

r\times_nC_r=(n-r+1)_nC_{r-1}

Divisez les deux côtés par «r» pour afficher la formule ■

Expression progressive 2: Diminuer n

_nC_r=_{n-1}C_{r-1}+_{n-1}C_r

Cela s'explique par le triangle de Pascal, mais je n'irai pas trop loin

Preuve

\begin{eqnarray}
_nC_r+_nC_{r-1} &=& \frac{n!}{r!(n-r)!}+\frac{n!}{(r-1)!(n-r+1)!}\\
&=& \frac{n!\times\{(n-r+1)+r\}}{r!(n-r+1)!}\\
&=& \frac{n!\times(n+1)}{r!(n-r+1)!}=\frac{(n+1)!}{r!(n+1-r)!}\\
&=& _{n+1}C_r
\end{eqnarray}

■

Ecrire en Python

Équation graduelle 1

_nC_r=_nC_{r-1}\times\frac{n-r+1}{r}

Basé sur, en tant que bord, c'est-à-dire en tant que paramètre de valeur initiale

_0C_r=_nC_0=1

Lorsqu'il est écrit récursivement en tant que fonction de return, il ressemble à ceci ([article précédent](http://qiita.com/kyoro1/items/eed40ab333a9f9fd8ede#python%E3%81%A7%E3%82%B0%E3%] 83% A9% E3% 83% 95% E3% 82% 92% E6% 8F% 8F% E3% 81% 84% E3% 81% A6% E3% 81% BF% E3% 82% 8B) Pareil que)

def comb1(n, r):
    if n == 0 or r == 0: return 1
    return comb1(n, r-1) * (n-r+1) / r 

Équation graduelle 2

_nC_r=_{n-1}C_{r-1}+_{n-1}C_r

Voici la valeur initiale définie en fonction de:

def comb2(n,r):
    if n < 0 or r < 0 or n < r: 
        return 0
    elif n == 0 or r == 0: 
        return 1
    return comb2(n-1,r-1)+comb2(n-1,r)

La raison pour laquelle le réglage de la valeur initiale est un peu plus compliqué que la formule graduelle 1 est que «n et r» changent.

Essaie

Déplaçons-le immédiatement.

>>> comb1(20,5)
15504.0
>>> comb2(20,5)
15504

Vérifier avec la fonction scipy existante

>>> import scipy.misc as scm
>>> scm.comb(20, 5)
15504.0

→ Ouais, c'est vrai ♪ (Ce n'est pas du tout une preuve, mais w)

Le site que j'ai utilisé comme référence

• Calculer la combinaison avec Python