Máy phát đệ quy trong Python

Question

Tôi đã viết một hàm để trả về một trình tạo chứa tất cả các kết hợp duy nhất của chuỗi con với độ dài đã cho có chứa nhiều hơn n thành phần từ một chuỗi chính.

Như một ví dụ:

nếu tôi có 'abcdefghi' và một cuộc điều tra của chiều dài của hai, và một ngưỡng cửa của 4 yếu tố cho mỗi danh sách tôi muốn nhận được:

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

My đầu tiên cố gắng giải quyết vấn đề này liên quan đến việc trả lại danh sách các danh sách. Điều này đã làm tràn bộ nhớ của máy tính. Là một giải pháp thứ cấp thô, tôi đã tạo ra một máy phát điện tương tự như vậy. Vấn đề là tôi đã tạo một trình tạo lồng nhau tự gọi. Khi tôi chạy hàm này, có vẻ như chỉ vòng quanh vòng lặp bên trong cho vòng lặp mà không thực sự gọi lại lần nữa. Tôi nghĩ rằng một máy phát điện sẽ đi trước đến tận đáy hố đệ quy khi cần thiết cho đến khi nó đạt được tuyên bố về sản lượng. Bất kỳ đầu mối gì đang xảy ra?

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 

Nếu sản lượng được thay đổi để in, nó hoạt động tốt! Tôi đánh giá cao bất kỳ sự giúp đỡ nào tôi có thể nhận được. Tôi nhận ra đây không phải là việc triển khai tối ưu loại vấn đề tìm kiếm này, có vẻ như trả lại danh sách các vị trí tìm thấy từ cuộc gọi cuối cùng của get_next_probe và lọc danh sách này cho các phần tử không chồng chéo new_last_probe.end sẽ hiệu quả hơn nhiều ... nhưng điều này dễ hơn cho tôi để viết. Bất kỳ đầu vào thuật toán nào vẫn sẽ được đánh giá cao.

Cảm ơn!

Answer 1

Tôi nghĩ rằng một máy phát điện sẽ đi trước như xa xuống hố đệ quy khi cần thiết cho đến khi nó đạt báo cáo kết quả năng suất

Nó sẽ recurse tốt, nhưng để có được giá trị yield ed để tuyên truyền lại ra bên ngoài, bạn cần phải làm điều đó một cách rõ ràng - giống như nếu nó là một return, bạn sẽ cần phải rõ ràng return kết quả của mỗi lần đệ quy. Vì vậy, thay vì:

self.get_next_probe(new_list, probes, unit_length) 

Bạn sẽ làm điều gì đó như:

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

Hoặc nếu bạn đang sử dụng Python 3.3 hoặc mới hơn, bạn cũng có thể làm điều này:

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