Lassen Sie uns eine Kombinationsberechnung mit Python durchführen

Problembewusstsein

In Vorheriger Artikel habe ich die Kombinationsberechnung in Python rekursiv durchgeführt, aber ich dachte, dass es andere Möglichkeiten gibt.

Überprüfung der Kombinationen

Es ist die Kombination, die ich in der Auftragskombination gelernt habe

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

Es war. Wenn hier "n <r" ist, ist die Kombination "0", dh

_0C_1=0

Ich verspreche "0", wenn es außerhalb der Definition liegt.

Wie eine allmähliche Formel

Dieses Mal möchte ich die Methode zum rekursiven Aufrufen der Funktion mit Python verwenden, um so etwas wie einen allmählichen Ausdruck vorzubereiten.

Zerfall 1: Verringere r

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

Beweis

Zunächst aus der Definition

_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}

Deshalb

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

Teilen Sie beide Seiten durch r, um die Formel anzuzeigen ■

Allmählicher Ausdruck 2: Verringern Sie "n"

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

Dies ist in Anbetracht von Pascals Dreieck selbsterklärend, aber ich werde nicht zu tief gehen.

Beweis

\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}

■

Schreiben Sie in Python

Allmähliche Gleichung 1

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

Basierend auf der Kante, dh der Anfangswerteinstellung

_0C_r=_nC_0=1

Wenn es rekursiv als Funktion für "return" geschrieben wird, sieht es so aus (vorheriger Artikel 83% A9% E3% 83% 95% E3% 82% 92% E6% 8F% 8F% E3% 81% 84% E3% 81% A6% E3% 81% BF% E3% 82% 8B) Gleich wie)

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

Allmähliche Gleichung 2

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

Der folgende Anfangssatz basiert auf:

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)

Der Grund, warum die Anfangswerteinstellung etwas komplizierter ist als die allmähliche Formel 1, ist, dass sich sowohl n als auch r ändern.

Ausprobieren

Bewegen wir es sofort.

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

Überprüfen Sie mit der vorhandenen Scipy-Funktion

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

→ Ja, das stimmt ♪ (Es ist überhaupt kein Beweis, aber w)

Die Seite, die ich als Referenz verwendet habe

• Kombination mit Python berechnen