Niedawno napisałem funkcję do generowania pewnych sekwencji z nietrywialnymi ograniczeniami. Problem przyszedł z naturalnym rekurencyjnym rozwiązaniem. Teraz zdarza się, że nawet przy stosunkowo małych danych wejściowych sekwencje mają kilka tysięcy, dlatego wolałbym użyć mojego algorytmu jako generatora, zamiast używać go do wypełniania listy wszystkimi sekwencjami.
Oto przykład. Załóżmy, że chcemy obliczyć wszystkie permutacje ciągu za pomocą funkcji rekurencyjnej. Poniższy algorytm naiwny pobiera dodatkowy argument „storage” i dołącza do niego permutację za każdym razem, gdy ją znajdzie:
def getPermutations(string, storage, prefix=""): if len(string) == 1: storage.append(prefix + string) # <----- else: for i in range(len(string)): getPermutations(string[:i]+string[i+1:], storage , prefix+string[i]) storage = [] getPermutations("abcd", storage) dla permutacji w pamięci: permutacja print (Proszę nie przejmować się nieefektywnością, to tylko przykład.)
Teraz chcę zmienić moją funkcję w generator, tj. uzyskać permutację zamiast dołączać ją do listy pamięci:
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]) dla permutacji w getPermutations("abcd"): permutacja print Ten kod nie działa ( funkcja zachowuje się jak em generator pty).
Czy czegoś mi brakuje? Czy istnieje sposób na przekształcenie powyższego algorytmu rekurencyjnego w generator bez zastępowania go algorytmem iteracyjnym?