Wie funktioniert dieses Programm zur Berechnung der Potenzmenge?
Folgendes Programm berechnet die Potenzmenge eines Feldes A mit der Länge n. Ich frage mich, wieso es funktioniert. Konkret was
for M in potenzmenge(n - 1, A):
tut und wie die def in einer for-Schleife umgesetzt wird, bzw. was da passiert.
Danke schon einmal. :)
Hier das Programm:
Def Potenzmenge (n, A):
If n == 0:
return([[]])
P = []
for M in potenzmenge(n - 1, A):
P.append(M)
P.append(M + [A[n - 1]])
return(P)
print (potenzmenge(3, [''a,'b','c'])
2 Antworten
Du solltest das hier auf gutefrage.net in ein Quelltext-Feld schreiben, damit beispielsweise die (in Python recht wichtigen) Einrückungen nicht verloren gehen.
Außerdem wird da wohl eher „Def“ statt „def“ und „if“ statt „If“ stehen. Und es wird auch entweder überall „potenzmenge“ oder überall „Potenzmenge“ stehen. Und es soll vermutlich auch „'a'“ statt „''a“ in der letzten Zeile stehen. Und in der letzten Zeile fehlt eine schließende Klammer. Denn sonst wird das Programm nicht funktionieren.
Ich gehe mal von dem folgenden Programm aus...
def potenzmenge(n, A) :
if n == 0:
return([[]])
P = []
for M in potenzmenge(n-1, A):
P.append(M)
P.append(M+[A[n-1]])
return(P)
print(potenzmenge(3, ['a', 'b', 'c']))
============
Nun zu deiner Frage...
Die Funktion potenzmenge(n, A) arbeitet rekursiv, ruft sich also während des Funktionsdurchlaufs selbst auf.
Der Funktionsaufruf potenzmenge(n, A) berechnet quasi die „Potenzmenge“ derjenigen „Menge“, die aus den ersten n Elementen der „Menge“ besteht. (Bemerkung: Eigentlich sind es hier ja keine Mengen, sondern Listen. Mengen hätte auch keine festgelegte Reihenfolge.)
Zunächst wird überprüft, ob man bei n == 0 angekommen ist, wo die Rekursion quasi ihren Endpunkt erreicht. Dort wird [[]] zurückgegeben, was quasi die Menge darstellen soll, welche die leere Menge enthält.
Jetzt kommt die Antwort auf deine eigentliche Frage...
In jedem sonstigen Rekursionsschritt wird nun potenzmenge(n-1,A) aufgerufen, was die „Potenzmenge“ der ersten n-1 Elemente von A liefert. Für jede „Menge“/Liste in dieser „Potenzmenge“ wird einmal die „Menge“/Liste M so wie sie ist verwendet, und einmal das Element A[n-1] zur „Menge“/Liste M hinzugefügt. Damit wird die Liste P befüllt. Am Ende der for-Schleife ist dann P die „Potenzmenge“ der ersten n Elemente von A, welche als Ergebnis zurückgeliefert wird.
======Ergänzung 1======
Ich bin im Folgenden mal komplett das Beispiel potenzmenge(3, ['a', 'b', 'c']) durchgegangen. Vielleicht hilft dir das, das Programm besser nachvollziehen zu können.
======Ergänzung 3======
Hier nochmal eine Übersicht, die dir evtl. weiterhelfen könnte...
Im Grund wird bei jedem Eintrag aus dem tieferen Rekursionsschritt einmal das Element 'a' bzw. 'b' bzw. 'c' nicht hinzugefügt und einmal hinzugefügt. So erhält man dann letztendlich alle möglichen Teilmengen.
======Ergänzung 2======
Im Grunde basiert die Rekursion darauf, dass gilt:
Im konkreten Fall quasi...
Ich frage mich, wieso es funktioniert, konkret was
for M in potenzmenge(n-1,A):
Tut
Die Funktion potenzmenge wird wieder aufgerufen, jedoch mit den Parametern n-1 und A. Die Funktion gibt eine Liste aus, die dann mit der for schleife durchiteriert wird.
Die Funktion funktioniert, da die Potenzmenge einer Menge A folgendes erfüllt:
Ist A eine nichtleere Menge, und ist a ein Element von A, dann gilt:
P(A) = P(A\{a}) vereinigt {{a} vereinigt M | M Element P(A\{a})}
Die erste Menge enthält nämlich alle Teilmengen von A, die a nicht enthalten und die zweite enthält alle Teilmengen von A, die a nicht enthalten. Damit kann man P(A) rekursiv bestimmen.