Onlangs heb ik een functie geschreven om bepaalde reeksen met niet-triviale beperkingen te genereren. Het probleem kwam met een natuurlijke recursieve oplossing. Nu gebeurt het dat, zelfs voor relatief kleine invoer, de reeksen enkele duizenden zijn, dus ik zou mijn algoritme liever als generator gebruiken in plaats van het te gebruiken om een lijst met alle reeksen te vullen.
Hier is dat Een voorbeeld. Stel dat we alle permutaties van een string met een recursieve functie willen berekenen. Het volgende naïeve algoritme neemt een extra argument "opslag" en voegt er een permutatie aan toe wanneer het er een vindt:
def getPermutations(string, storage, prefix=""): if len(string) == 1: storage.append(prefix + string) # <---- else: for i in range(len(string)): getPermutaties(string[:i]+string[i+1:], storage , prefix+string[i]) storage = [] getPermutations("abcd", storage) voor permutatie in opslag: print permutatie (Maak je geen zorgen over inefficiëntie, dit is alleen een voorbeeld.)
Nu wil ik van mijn functie een generator maken, dwz een permutatie opleveren in plaats van deze aan de opslaglijst toe te voegen:
def getPermutations(string , prefix=""): if len(string) == 1: opbrengst prefix + string # <---- else: for i in range(len(string)): getPermutaties(string[:i]+string [i+1:], prefix+string[i]) voor permutatie in getPermutations("abcd"): print permutatie Deze code werkt niet ( de functie gedraagt zich als een em pty generator).
Mis ik iets? Is er een manier om het bovenstaande recursieve algoritme in een generator te veranderen zonder het te vervangen door een iteratief algoritme?