Das deutsche Python-Forum

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...)

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)))

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...)

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?

Das deutsche Python-Forum

potenzmenge

potenzmenge

Re: potenzmenge

Re: potenzmenge

Re: potenzmenge