Können Sie erklären, diese rekursive "n wählen k" - code für mich?

Hier ist der code, um eine Teilmenge problem mit Argumente n und k. n stellt die Gesamtzahl der Studierenden und k repräsentiert die Menge der Studenten, die ich will, um aus der n. Der code versucht die Anzahl der möglichen Kombinationen von ziehen k Anzahl der Studierenden aus n Anzahl der Studierenden.

def subset(n, k): 
    if k == 0:
        return 1
    if n == k:
        return 1
    else:
        return subset(n-1, k-1) + subset(n-1, k)

Ich verstehe den ersten Teil des rekursiven Aufrufs, aber ich habe Schwierigkeiten zu verstehen, die + Teilmenge(n-1, k) Teil. Kann jemand erklären mir das an?

InformationsquelleAutor Billy Thompson | 2012-10-19
  1. 21

    Ist die Rekursion basiert auf einer einfachen Beobachtung, für die ich geben eine kombinatorische argument, warum es ist wahr, eher als eine mathematische Beweise durch Formeln.

    Wann immer Sie wählen k Elemente aus n gibt es zwei Fälle:

    1. Wählen Sie element #n
    2. Sie nicht wählen, element #n

    Da diese Ereignisse sich gegenseitig ausschließen, die Summe der Kombinationen ist gegeben durch die Menge der Kombinationen bei der Auswahl #n, und diejenigen, die, wenn Sie nicht wählen #n.

    Wahl element #n

    Da haben wir schon gewählt, ein element, wir brauchen nur wählen Sie eine andere k-1 Elemente. Auch, da wir beschlossen haben, auf ein element – ob es enthalten ist oder nicht – schon, wir müssen uns nur überlegen, die restlichen n-1 Elemente.

    Damit, die Menge von Kombinationen für die Auswahl element #n ist gegeben durch

        subset(n - 1, k - 1)

    Nicht auswählen element #n

    Gibt es noch k Elemente zu wählen, da wir aber bereits unsere Meinung über element #n es bleiben nur n - 1 Elemente zur Auswahl. Also:

        subset(n - 1, k)

    Die base-case -

    Die Rekursion nutzt die Tatsache, dass wir in der Regel unterscheiden zwischen zwei Situationen, Lösungen, wo element n ist Teil der Lösung, und diejenigen, wo es nicht ist.

    Jedoch eine solche Unterscheidung nicht immer gemacht werden:

    • Bei der Auswahl aller Elemente (entsprechend zu Fall n == k im code unten)
    • oder bei der Auswahl keine Elemente überhaupt (entsprechend zu Fall k == 0 im code unten)

    In diesen Fällen gibt es nur genau eine Lösung, damit

    if k == 0:
    return 1
if n == k:
    return 1

    Dass es funktioniert

    Zu tun, müssen wir uns selbst davon überzeugen (oder zu beweisen), dass die base-case-ist immer der hit bei einem gewissen Punkt.

    Lassen Sie uns davon ausgehen, dass n < k irgendwann. Da nach unserer Annahme n war ursprünglich größer oder gleich k es muss wurden einige Punkt, wo n = k, weil n und k Rückgang im unisono oder nur n verringert sich um eins, d.h. es folgt

    Impliziert dies, dass es gewesen sein muss, einen Anruf zu subset(n - 1, k) es passieren, dass n nimmt unterhalb k. Dies ist jedoch nicht möglich, da haben wir eine Basis Fall auf n = k wo wir wieder eine Konstante 1.

    Schließen wir, dass entweder n sinkt irgendwann so, dass n = k oder zu verringern, im Einklang genau k mal so, dass k = 0.

    So, die base-case funktioniert.

    InformationsquelleAutor phant0m
  2. 1

    Dies ist mehr ein mathematisches problem und nicht eine Frage der Programmierung. Was Sie tun, ist die Berechnung der Binomial-Koeffizienten, die Formel ist

    (n, k) = (n-1, k-1) + (n-1, k) with all (n, 0) and (n, n) having a value of 1.

    Finden Sie hier für eine vollständige Erklärung. Eine rekursive Lösung gesehen werden kann hier. Bei dem genannten link geht ungültige such einfach mit Google. Ich bezweifle, dass Sie eine bessere Erklärung, als nach dem Lesen dieses Artikels auf Wikipedia.

    • Ich bin wirklich einfach nur verwirrt über die Rekursion, obwohl.
    InformationsquelleAutor hochl
  3. 0

    Code-fragment:

    if k == 0:
    return 1
if n == k:
    return 1

    verwendet zwei kombinatorische Fakten:

    nC0 = 1
nCn = 1

    als Basis Fällen.

    Nächsten, folgenden rekursiven aufrufen:

    return subset(n-1, k-1) + subset(n-1, k)

    direkt übersetzt die folgende Tatsache in den code:

    nCr = (n-1)C(k-1) + (n-1)Ck

    Wenn Sie Schwierigkeiten haben, zu verstehen, wie obige Gleichung gilt, dann Lesen Sie weiter:
    In nCr, wählen wir r Elemente aus n. Die Entscheidungen können klassifiziert werden in zwei sich gegenseitig ausschließende Klassen, wenn wir betrachten ein bestimmtes Objekt:

    • Element tritt unter r ausgewählt

      In diesem Fall müssen wir wählen, die restlichen r-1 Elemente aus den verbleibenden n-1 Elemente. Dies kann man in (n-1)C(k-1).

    • Element nicht auftreten, unter r ausgewählt

      In diesem Fall haben wir zu wählen, alle von r Elementen aus den verbleibenden n-1 Elemente, die getan werden kann (n-1)Ck Möglichkeiten.

    Fügen wir diese beiden, wie ich bereits sagte, diese beiden Klassen sich gegenseitig ausschließen und daher zusammen bildet die gesamten Möglichkeiten der Auswahl von r Elementen aus n.

    InformationsquelleAutor Mahesha999
Schreibe einen Kommentar