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

Recommended Posts

Faisons un calcul de combinaison avec Python
Créer un bookmarklet en Python
Faisons une interface graphique avec python.
Faisons un service de vente au comptant 4 (en Python mini Hack-a-thon)
Faisons un jeu de shiritori avec Python
Faisons la voix lentement avec Python
Créez un framework Web avec Python! (1)
Faisons un bot Twitter avec Python!
Créez un framework Web avec Python! (2)
Calculer les dates en Python
Copiez la liste en Python
Créez un jeu Janken en une seule ligne (python)
Faisons quelques exemples de traitement des notifications en Python
Créez un tracé de R semblable à un joyplot avec python
Faisons un module pour Python en utilisant SWIG
Voyons comment utiliser def en python
Faisons un robot Discord.
Essayez de créer un module Python en langage C
Créer une fonction en Python
Créer un dictionnaire en Python
Je veux écrire en Python! (2) Écrivons un test
Calcul de la valeur de jeu de cisaillement en Python
Créez un Slackbot simple avec un bouton interactif en python
[Jouons avec Python] Créer un livre de comptes de ménage
Essayez de créer un jeu simple avec Python 3 et iPhone
[Pour jouer] Essayez de faire de Yuma un robot LINE (Python)
Faites une loterie avec Python
Rendre Opencv disponible en Python
Dessinez un cœur en Python
[Super facile] Faisons un LINE BOT avec Python.
Trouvons le rapport de circonférence avec Python
Faisons un programme cron en Java! !! (Planificateur de tâches)
Créons un client de socket Web avec Python. (Authentification par jeton d'accès)
Créer un tableau de multiplication de chaque élément dans une feuille de calcul (Python)
Créons un script qui s'enregistre avec Ideone.com en Python.
J'ai fait un chronomètre en utilisant tkinter avec python
Je veux ajouter un joli complément à input () en python
Faisons une rumba distante [Matériel]
Probablement dans un serpent Nishiki (Titre original: Peut-être en Python)
[python] Gérer les fonctions dans une liste
Faisons une rumba distante [Logiciel]
Lançons "python -m antigravity" en python
Créer un conteneur DI avec Python
Faisons un service de vente au comptant 2
Dessinez une matrice de diagramme de dispersion avec python
ABC166 en Python A ~ C problème
Faisons une rupture de bloc avec wxPython
Ecrire des algorithmes A * (A-star) en Python
Faisons un service de vente au comptant 1
Essayons Fizz Buzz avec Python
Rendre la sortie standard non bloquante en Python
Créer un fichier binaire en Python
python / Créer un dict à partir d'une liste.
[Python] Faire de la fonction une fonction lambda
Créer un système de recommandation avec python
Résoudre ABC036 A ~ C avec Python
Ecrire un graphique à secteurs en Python