Rekursions-Nachhilfe

[Bob Billsworth]

Hallo Zusammen

Ich möchte die unterschiedlichen Kombinationen prozentualer Gewichtungen von n Elementen in einer Liste speichern. Dabei gilt: E1 + E2 + … + En = 1 bzw. 100%. Des Weiteren will ich möglichst unpythonisch programmieren, da das Programm später in JavaScript übertragen werden soll.

Zur Lösung des Ganzen ist mir bisher nur eine brute-force-Methode vermittels Rekursion eingefallen. Wenn ich print(x) hinzunehme, zeigt er mir das Gewollte. An die Liste (permut) wird allerdings nur und an sich fälschlicher Weise [0,0,0,0] angehängt.

Vielen Dank im Voraus für Eure Antworten.

Code: Alles auswählen

def deepblue(start,items,line,skala):
    if start < items:
        for i in range(len(skala)):
            line[start] = skala[i]
            x = deepblue(start+1,items,line,skala)
            #print(x)
            if (round(sum(x),2) == 1.0) and (x not in permut):
                permut.append(x)                  
        return line
    else:
        return line

global permut
permut = []

items = 4
step = 0.05

total = 1
mini = 0
skala = []
line = []

while total >= mini:
    skala.append(total)
    total = round(total-step,2)

for i in range(items):
    line.append(0)

deepblue(0,items,line,skala)

for line in permut:
    print(line)

[BlackJack]

@Bob Billsworth: Du hast da ein Problem das Du auch in JavaScript hättest: Du arbeitest nur mit einer einzigen Liste die unter anderem an `line` gebunden ist und die *veränderst* Du. Wenn die an `permut` angehängt wird, wird sie danach auch weiterhin fröhlich von anderen rekursiven Aktivierungen Deiner Funktion verändert. Wenn Du ein Ergebnis hast das angehängt werden soll, dann solltest Du davon eine Kopie erstellen, also zum Beispiel einfach ``permut.append(list(x))``. Wobei das herumreichen von `line` und binden an `x` nicht so viel Sinn macht, denn das ist ja in jedem rekursive Aufruf immer das selbe Objekt, also mindestens den Namen `x` solltest Du loswerden damit ein Leser nicht fälschlicherweise den Eindruck bekommt `x` und `line` seien jemals verschiedene Objekte.

Python eignet sich IMHO nicht wirklich gut für das Prototyping von JavaScript-Code weil die Ansätze Iterationen zu abstrahieren grundverschieden sind. In Python funktioniert alles über externe Iteratoren wo sich der Code der die Werte verarbeitet die Werte heraus holt und bei JavaScript über interne Iteratoren wo man den Code der die Werte verarbeitet übergibt. Du magst da zwar etwas schreiben was nicht „pythonisch“ ist mit dem Ziel einen Prototyp für JavaScript zu schreiben, aber wenn Du den dann zu JavaScript überführst werden JavaScript-Programmierer das als nicht wirklich idiomatisches JavaScript erkennen.

``global`` auf Modulebene hat übrigens keinerlei Effekt. Die Zeile kannst Du ersatzlos streichen.

[BlackJack]

Auch in JavaScript sind ”modulglobale” Variablen nicht gern gesehen, insbesondere weil die auf der Ebene in JavaScript tatsächlich global sind weil eine Quelltextdatei dort keinen eigenen Namensraum bildet. Im Gegensatz zu Python und wegen der internen Iteratoren sind lokale Funktionen in JavaScript Normalität. Und selbst in Python macht das bei rekursiven Lösungen Sinn Werte die sich alle rekursiven Aufrufe teilen über ein „closure“ zur Verfügung zu stellen statt sie bei jedem Aufruf weiter durch zu reichen. Letztendlich würde für die rekursive Funktion selbst nur der `start`-Index übrig bleiben.

Den Namen `items` fand ich verwirrend weil der normalerweise für eine Sequenz oder einen Iterator mit Elementen steht, also für die Elemente selbst, und nicht für deren Anzahl. Ich habe auch ein paar andere Namen in der rekursiven Funktion angepasst und es doch etwas in Richtung Python verändert, weil 1:1 kann man es sowieso nicht übernehmen und aus einer idiomatischen Python-``for``-Schleife eine Zählschleife in JavaScript zu machen ist ja kein Beinbruch. Zwischenstand wäre das hier:

Code: Alles auswählen

def find_solutions(length, skala):
    results = list()
    result = [0] * length

    def deepblue(start):
        if start < length:
            for value in skala:
                result[start] = value
                deepblue(start + 1)
                if round(sum(result), 2) == 1.0 and result not in results:
                    results.append(list(result))

    deepblue(0)
    return results


def main():
    item_count = 4
    step = 0.05
    total = 1
    mini = 0
    skala = []

    while total >= mini:
        skala.append(total)
        total = round(total - step, 2)

    permut = find_solutions(item_count, skala)
    for line in permut:
        print(line)


if __name__ == '__main__':
    main()