rekursive generator-Funktion definieren

[Goswin]

Ich versuche vergeblich, eine generator-Funktion zu schreiben, welche "dasselbe" macht wie folgende list-Funktion, nur eben ohne wie hier eine Liste aufzubauen:

Code: Alles auswählen

def mloop_lst(top_lst,val_tpl=(),ausgabe_lst=[]):
   for val in range(top_lst[0]+1):
      if len(top_lst)>1:
         mloop_lst(top_lst=top_lst[1:],val_tpl=val_tpl+(val,))
      else:
         ausgabe_lst.append(val_tpl+(val,))
   return ausgabe_lst

for val_tpl in mloop_lst(top_lst=[2,4,3]):
   print(val_tpl)

Erwünscht wäre es, die auszugebende Tupel nacheinander aufzubauen, ohne eine Liste ausgabe_lst zu erzeugen. Meine vergeblichen Versuch gehen in Richtung:

Code: Alles auswählen

#FALSCH!
def mloop_gen(top_lst,val_tpl=()):
   for val in range(top_lst[0]+1):
      if len(top_lst)>1:
         mloop_gen(top_lst=top_lst[1:],val_tpl=val_tpl+(val,))
      else:
         yield val_tpl+(val,)

for val_tpl in mloop_gen(top_lst=[2,4,3]):
   print(val_tpl)

[mutetella]

Code: Alles auswählen

itertools.product(range(3), range(5), range(4))

mutetella

[BlackJack]

@Goswin:

Code: Alles auswählen

from itertools import product

def mloop(top):
    return product(*(range(n + 1) for n in top))

Edit: Übrigens ist Deine Funktion fehlerhaft. Ruf die mal mehr als einmal auf. Veränderbare Objekte als Default-Argumente sind selten eine gute Idee.

[Goswin]

Vielen Dank für den Hinweis auf itertools; das löst mein Problem.
(Meine Unkenntnis bezüglich der yield-Funktion ist zwar noch dieselbe wie vorher, aber damit störe ich euch bei der nächsten Hürde )

Übrigens ist Deine Funktion fehlerhaft. Ruf die mal mehr als einmal auf. Veränderbare Objekte als Default-Argumente sind selten eine gute Idee.

Sehr richtig. Ich hoffe, so wie folgt wäre sie in Ordnung:

Code: Alles auswählen

def mloop_lst(top_lst,val_tpl=(),ausgabe_lst=None):
   if ausgabe_lst==None: ausgabe_lst = []
   for val in range(top_lst[0]+1):
      if len(top_lst)>1:
         mloop_lst(top_lst=top_lst[1:],val_tpl=val_tpl+(val,))
      else:
         ausgabe_lst.append(val_tpl+(val,))
   return ausgabe_lst

[BlackJack]

@Goswin: Dass das noch nicht ganz ausreicht hättest Du durch ausprobieren schnell heraus gefunden. Du musst jetzt das letzte Argument auch beim rekursiven Aufruf explizit mitgeben, sonst ist es dort ja immer `None`.

Bei Deinem Umstieg auf die Generatorfunktion hattest Du vergessen die ganzen Ergebnisse des rekursiven Aufrufs auch zu ``yield``\en:

Code: Alles auswählen

def mloop(top, values=()):
    for value in range(top[0] + 1):
        new_values = values + (value,)
        if len(top) > 1:
            for result in mloop(top[1:], new_values):
                yield result
        else:
            yield new_values

[snafu]

Wobei man den Programmfluss jetzt noch so ändern könnte, dass innerhalb der Schleife nicht ständig auf `len(top) > 1` geprüft wird, da dies quasi eine Konstante ist. Diesen Test kann man zu Beginn der Funktion machen und sich dann je nach Ergebnis für eine von zwei (noch zu implementierenden) `for`-Schleifen für den weiteren Verlauf entscheiden. Ich gebe aber zu, dass dies komplexer und damit auch schwerer zu lesen wäre.

EDIT: Ungetestet:

Code: Alles auswählen

def mloop(top, values=()):
    new_value_iter = (values + (value,) for value in range(top[0], + 1))
    if len(top) > 1:
        for new_values in new_value_iter:
            for result in mloop(top[1:], values):
                yield result
    else:
        for new_values in new_value_iter:
            yield new_values

Der `else`-Zweig wäre im Übrigen wohl auch ein sinnvoller Anwendungsfall für das in Python 3.3 eingeführte yield from.

[BlackJack]

@snafu: Warum nur der ``else``-Zweig?

[snafu]

@snafu: Warum nur der ``else``-Zweig?

Ich wüsste auf Anhieb jedenfalls nicht, wie man den anderen Zweig mit `yield from` ausdrücken sollte.

[BlackJack]

@snafu: Häh? Das ist doch exakt das selbe Muster im Quelltext: ``yield from mloop(top[1:], values)``.

[snafu]

Ja, stimmt. Und ich hab oben einen Fehler gemacht: Beim rekursiven Aufruf von `mloop()` muss natürlich `new_values` übergeben werden und nicht `values`...

EDIT: Nochmal komplett (ab Python 3.3):

Code: Alles auswählen

def mloop(top, values=()):
    def iter_new_values():
        for value in range(top[0] + 1):
            yield values + (value,)

    if len(top) > 1:
        for new_values in iter_new_values():
            yield from mloop(top[1:], new_values)
    else:
        yield from iter_new_values()

Wobei jetzt wieder überflüssigerweise die innere Funktion jedes Mal neu definiert wird. Den Teil kann man natürlich auch auf Modulebene verlagern. Wenn man jetzt wirklich auf (potenzielle) Mikro-Optimierungen aus ist, dann würde man vermutlich sowieso eher den von mir zuvor gezeigten Generator verwenden, um sich den Funktionsaufruf zu sparen. ;P

EDIT2: Blödsinn, das geht nicht auf Modulebene, höchstens innerhalb einer Klasse. Schön kompliziert. Ich glaub, ich geh jetzt lieber mal schlafen.