Python: utilizzo di un algoritmo ricorsivo come generatore

| | | | | | | | | | | |

Recentemente ho scritto una funzione per generare determinate sequenze con vincoli non banali. Il problema è arrivato con una soluzione ricorsiva naturale. Ora capita che, anche per input relativamente piccoli, le sequenze siano diverse migliaia, quindi preferirei usare il mio algoritmo come generatore invece di usarlo per riempire una lista con tutte le sequenze.

Ecco un esempio. Supponiamo di voler calcolare tutte le permutazioni di una stringa con una funzione ricorsiva. Il seguente algoritmo ingenuo prende un argomento aggiuntivo "storage" e vi aggiunge una permutazione ogni volta che ne trova una:

def getPermutations(string, storage, prefix=""): if len(string) == 1: storage.append(prefisso + stringa) # <----- else: for i in range(len(string)): getPermutations(string[:i]+string[i+1:], storage , prefix+string[i]) storage = [] getPermutations("abcd", storage) per la permutazione in storage: print permutation 

(Per favore non preoccuparti dell'inefficienza, questo è solo un esempio.)

Ora voglio trasformare la mia funzione in un generatore, cioè produrre una permutazione invece di aggiungerla alla lista di archiviazione:

def getPermutations(string , prefix=""): if len(string) == 1: yield prefix + string # <----- else: for i in range(len(string)): getPermutations(string[:i]+string [i+1:], prefix+string[i]) per la permutazione in getPermutations("abcd"): print permutation 

Questo codice non funziona ( la funzione si comporta come un em pty generator).

Mi sfugge qualcosa? C'è un modo per trasformare l'algoritmo ricorsivo di cui sopra in un generatore senza sostituirlo con uno iterativo?