Liste rekursiv durchlaufen

[joheu01]

Hallo, zusammen,

ich sitze an einem Problem, bei dem ich eine gegebene sortierte Liste mit nicht notwendigerweise verschiedenen Zahlen als Listeneinträge in einer Funktion durchlaufe und eine Liste zurückgebe, die alle möglichen Summen aus n nicht notwendigerweise verschiedenen Listeneinträgen
enthält. Gegeben sei folgende Liste: [1,2,3,4,5,6].

Bei n=1 wäre die zurückgegebene Liste auch wieder [1,2,3,4,5,6],
bei n=2 dementsprechend
[1+1, 1+2, 1+3, 1+4, 1+5, 1+6, 2+2, 2+3 ,2+4, 2+5, 2+6, 3+3, 3+4 ,3+5, 3+6, 4+4, 4+5, 4+6, 5+5, 5+6, 6+6] (In Wirklichkeit enthält die Liste die Ergebnisse der Additionen, die Darstellung als Rechnung soll nur dem Verständnis des Problems dienen.)

Mein rekursiver Ansatz sieht folgendermaßen aus:

Code: Alles auswählen

def durchlaufeListe(liste, anzahl, zahlcurr, listeAusgabe):
    if anzahl == 1:
        for m in liste:
            listeAusgabe.append(m)
        return listeAusgabe
    else:
        for zahlcurr in range(anzahl+1):
            if zahlcurr == 1:
                for n in range(len(durchlaufeListe(liste, anzahl-1,zahlcurr,listeAusgabe))):
                    listeAusgabe.append(durchlaufeListe(liste,anzahl-1,zahlcurr,listeAusgabe)[n]+durchlaufeListe(liste, 1,zahlcurr,listeAusgabe)[n])
            else:
                for p in range(len(durchlaufeListe(liste,anzahl-1,zahlcurr,listeAusgabe).pop(zahlcurr-1))):
                    listeAusgabe.append(durchlaufeListe(liste,anzahl-1,zahlcurr,listeAusgabe).pop(zahlcurr-1)[p]+durchlaufeListe(liste,1,zahlcurr,listeAusgabe).pop(zahlcurr-1)[p])
        return listeAusgabe

Hierbei steht anzahl für die Zahl, wie viele Listeneinträge die Summen enthalten sollen und zahlcurr für die Zahl, der wievielte Summand momentan aufsummiert wird.

Ich würde die Funktion also in Abhängigkeit einer bestimmten Liste und der Anzahl aufrufen. Zahlcurr wäre beim Aufruf 1 und listeAusgabe die leere Liste.

Leider funktioniert das noch nicht ganz. Kann mir dabei jemand behilflich sein?

Vielen Dank im Voraus.

[Sirius3]

Für das Problem benutzt man `itertools.combinations_with_replacement`:

Code: Alles auswählen

def summiere_zahlen(zahlen, anzahl):
    return list(map(sum, combinations_with_replacement(zahlen, anzahl)))

In Deinem Code benutzt Du das Argument zahlcurr gar nicht.
Die Funktion aufzurufen, nur um die Länge der Elemente zu bestimmen und dann nochmal für jedes Element die gesamte Ergebnisliste zwei mal aufzurufen, nur im daraus EIN Element zu holen, ist ziemliche Verschwendung.
Vor allem, weil Du eine globale Liste `listeAusgabe` hast, die bei jedem Aufruf immer länger wird.
Also sollte für jede "Anzahl" in Deinem Code auch nur ein rekursiver Aufruf stehen.

Da Du noch so weit von einem richtigen Code entfernt bist, hier mal eine kleine Starthilfe:

Code: Alles auswählen

def summiere_zahlen(zahlen, anzahl):
    if anzahl == 1:
        return list(zahlen)
    else:
        vorlaeufiges_ergebnis = summiere_zahlen(zahlen, anzahl - 1)
        # hier musst Du irgendwas mit zahlen und vorlaeufiges_ergbnis machen
        ...
        return ergebnis

[joheu01]

Danke erstmal,

hätte ich gewusst, dass es dafür eine vordefinierte Funktion gibt, hätte ich mir die Mühe ja gar nicht machen brauchen
Für den Reiz probiere ich mich trotzdem nochmal an der eigenen Implementierung xD