파이썬의 재귀 생성자

Question

기본 문자열의 n 개 요소 이상을 포함하는 주어진 길이의 모든 하위 문자열 조합을 포함하는 생성기를 반환하는 함수를 작성했습니다. 그림으로

:

내가 좀하고 싶습니다 'ABCDEFGHI'두 개의 길이의 프로브 및 목록 당 4 개 요소의 문턱이있는 경우 :

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

내 첫에게 목록의 목록을 반환하는 것과 관련된이 문제를 시도하십시오. 결국 컴퓨터의 메모리가 넘쳐났습니다. 원유의 부차적 인 해결책으로서, 비슷한 것을하는 생성기를 만들었습니다. 문제는 자체 호출하는 중첩 된 생성기를 만들었습니다. 이 함수를 실행하면 실제로 자체를 다시 호출하지 않고 내부 for 루프를 반복하는 것처럼 보입니다. 나는 발전기가 항복 선언문을 칠 때까지 필요에 따라 재귀 구멍보다 먼 곳에 선행한다고 생각했다. 무슨 일이 일어나고 있는지 어떤 단서가 있습니까?

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 

출력량이 인쇄로 변경되면이 기능이 정상적으로 작동합니다. 내가 얻을 수있는 도움을 주시면 감사하겠습니다. 이것이 검색 문제의 이런 유형의 최적의 구현이 아니라는 것을 알고 있습니다. get_next_probe의 마지막 호출에서 발견 된 위치 목록을 반환하고 new_last_probe.end와 겹치지 않는 요소에 대해이 목록을 필터링하는 것이 훨씬 효율적입니다. ... 그러나 이것은 나를 쓰는 것이 훨씬 쉬웠다. 모든 알고리즘 입력은 여전히 ​​인정 될 것입니다.

감사합니다.

Answer 1

나는 그것이 yield 문

그것은 잘 재귀하지만, 바깥쪽으로 다시 전달 될하기 위해 yield 에드 값을 얻기 위해 충돌 때까지 발전기가 필요에 따라 재귀 구멍 아래까지 선행 것이라고 생각 명시 적으로 수행해야합니다. return처럼, 각각의 재귀 결과를 명시 적으로 return해야합니다. 그래서, 대신 : 파이썬 3.3 이상을 사용하는 경우, 당신은이 작업을 수행 할 수 있습니다 또는

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

:

self.get_next_probe(new_list, probes, unit_length) 

당신이 좋아하는 일을 할 것

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