potenzmenge

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
alX1111
User
Beiträge: 6
Registriert: Donnerstag 22. April 2021, 18:02

hallo zusammen!
ich probier schon ewig rum - wäre Wahnsinn, wenn jemand was dazu sagen könnte!!

ich habe eine funktion programmiert, die mir bei eingabe einer liste deren potenzmenge ausgibt. folgender code macht was er soll:

Code: Alles auswählen

def getAllSubsets(lst):
    if not lst:
        return [[]]

    Rec = getAllSubsets(lst[1:])
    withFirst = [[lst[0]] + rest for rest in Rec]
    withoutFirst = Rec
    return withFirst + withoutFirst

print(getAllSubsets([1, 2, 3]))
jetzt möchte ich dasselbe machen - auch rekursiv - allerdings soll die funktion nun nicht die liste entgegennehmen, sondern nur eine natürliche zahl n,
die für die obere grenze der zahlenfolge aller natürlicher zahlen <= n steht. also eingabe n=3 soll für die liste [1,2,3] stehen, etc.
ich sehe einfach den fehler in folgendem code nicht!!??

Code: Alles auswählen

def potenzmenge(n):
    if n == 0:
        return [[]]

    second = [[]]
    for i in range(0, len(potenzmenge(n - 1))):
        second[I].append(potenzmenge(n - 1)[i] + [n])
    return potenzmenge(n - 1) + second

print(potenzmenge(3))

(unabhängig davon, dass der dreimalige rekursive aufruf noch durch eine variable ersetzt werden sollte...)
Sirius3
User
Beiträge: 17703
Registriert: Sonntag 21. Oktober 2012, 17:20

Variablennamen und Funktionen werden komplett klein geschrieben.
Mit itertools.combinations geht das ganze deutlich einfacher:

Code: Alles auswählen

from itertools import chain, combinations

def get_all_subsets(values):
    return chain.from_iterable(combinations(values, k) for k in range(len(values) + 1))

print(list(get_all_subsets([1,2,3)))
Bei Deinem Code mußt Du im ersten Fall doch nur lst durch n ersetzen:

Code: Alles auswählen

def get_all_subsets(n):
    if n == 0:
        return [[]]

    result = get_all_subsets(n - 1)
    return [[n] + rest for rest in result] + result

print(get_all_subsets(3))
In Deinem zweiten Code ist es erstens ziemliche Verschwendung für ein einzelnes Element jeweils die komplette Subliste zu erzeugen. Zweitens ist das iterieren über einen Index eh ein Antipattern.
I ist nicht definiert.
Wenn ich das Umschreibe komme ich auf ungefähr das:

Code: Alles auswählen

def potenzmenge(n):
    if n == 0:
        return [[]]

    second = [[]]
    for menge in potenzmenge(n - 1):
        second.append(menge)
        second[0].append(menge + [n])
    return second

print(potenzmenge(3))
Da stellt sich mir die Frage, warum Du alles in die erste Liste von second verschachtelst?
Läßt man diese innere Liste einfach weg, kommt man schon auf das richtige Ergebnis:

Code: Alles auswählen

def potenzmenge(n):
    if n == 0:
        return [[]]

    second = []
    for menge in potenzmenge(n - 1):
        second.append(menge)
        second.append(menge + [n])
    return second

print(potenzmenge(3))
Auch bei dieser Variante wäre ein Generator speicherschonender:

Code: Alles auswählen

def potenzmenge(n):
    if n == 0:
        yield []
    else:
        for menge in potenzmenge(n - 1):
            yield menge
            yield menge + [n]

print(list(potenzmenge(3)))
alX1111
User
Beiträge: 6
Registriert: Donnerstag 22. April 2021, 18:02

vielen dank für die ausführliche antwort! ein traum!!
hat mir echt weitergeholfen.
(nur warum die iteration über einen index ein antipattern ist hat sich mir noch nicht erschlossen...)
Benutzeravatar
pillmuncher
User
Beiträge: 1482
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

alX1111 hat geschrieben: Samstag 8. Mai 2021, 23:14 nur warum die iteration über einen index ein antipattern ist hat sich mir noch nicht erschlossen...
Vergleiche:
  • Gehe der Reihe nach über die Elemente der Liste L, indem du die Indizes i von 1 bis len(L) erzeugst, addressiere jeweils das Element an der Stelle i und mache mit ihm dieses-und-jenes.
  • Gehe der Reihe nach über die Elemente der Liste L und mache mit jedem Element dieses-und-jenes.
Was klingt für dich einfacher? Warum? Interessiert dich die Selle, an der ein Element steht, oder willst du nur einfach mit jedem Element der Reihe nach dieses-und-jenes tun?
In specifications, Murphy's Law supersedes Ohm's.
Antworten