Generadores recursivos en Python

Question

Escribí una función para devolver un generador que contiene cada combinación única de subcadenas de una longitud determinada que contiene más de n elementos de una cadena primaria.

A modo de ejemplo:

si tengo 'abcdefghi' y una sonda de longitud de dos, y un umbral de 4 elementos por lista me gustaría obtener:

['ab', 'cd', 'ef', 'gh'] 
['ab', 'de', 'fg', 'hi'] 
['bc', 'de', 'fg', 'hi'] 

Mi primera intento de este problema implica regresar una lista de listas. Esto terminó desbordando la memoria de la computadora. Como solución secundaria bruta, creé un generador que hace algo similar. El problema es que creé un generador anidado que se llama a sí mismo. Cuando ejecuto esta función, parece que simplemente recorre el ciclo interno for sin volver a llamarse a sí mismo. Pensé que un generador precedería tan abajo en el agujero de recursión como fuera necesario hasta que alcanzara la declaración de rendimiento. ¿Alguna pista de lo que está pasando?

def get_next_probe(self, current_probe_list, probes, unit_length): 
    if isinstance(current_probe_list, list): 
     last_probe=current_probe_list[-1] 
     available_probes = [candidate for candidate in probes if candidate.start>last_probe.end] 
    else: 
     available_probes = [candidate for candidate in probes if candidate.start<unit_length] 

    if available_probes: 

     max_position=min([probe.end for probe in available_probes]) 
     available_probes2=[probe for probe in available_probes if max_position+1>probe.start] 

     for new_last_probe in available_probes2: 
      new_list=list(current_probe_list) 
      new_list.append(new_last_probe) 
      self.get_next_probe(new_list, probes, unit_length) 

    else: 
     if len(current_probe_list)>=self.num_units: 
      yield current_probe_list 

Si se cambia el rendimiento para imprimir esto funciona bien! Apreciaría cualquier ayuda que pudiera obtener. Me doy cuenta de que esto no es una implementación óptima de este tipo de problema de búsqueda, parece que devolver una lista de posiciones encontradas de la última llamada de get_next_probe y filtrar esta lista para los elementos que no se superponen new_last_probe.end sería mucho más eficiente ... pero esto fue mucho más fácil para mí escribir. Cualquier entrada de algoritmo aún sería apreciada.

Gracias!

Answer 1

pensé que un generador precedería a lo más abajo que el agujero recursividad como sea necesario hasta que llegó la sentencia yield

Será recursivo bien, pero para obtener el valor yield ed a propagar hacia atrás hacia el exterior, debe hacerlo explícitamente, al igual que si fuera return, necesitaría explícitamente return el resultado de cada recursión. Así, en lugar de:

self.get_next_probe(new_list, probes, unit_length) 

Se podría hacer algo como:

for val in self.get_next_probe(new_list, probes, unit_length): 
    yield val 

O si usted está usando Python 3.3 o posterior, también se puede hacer esto:

yield from self.get_next_probe(new_list, probes, unit_length)