Python中的递归生成器

Question

我编写了一个函数来返回一个生成器,该生成器包含给定长度的每个子串的唯一组合,该子串包含来自主串的n个元素.

作为说明:

如果我有'abcdefghi'和长度为2的探测器,并且每个列表的阈值为4个元素我想得到:

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

我对此问题的第一次尝试涉及返回列表列表.这最终溢出了计算机的内存.作为一个粗略的二次解决方案,我创建了一个类似的东西.问题是我创建了一个自己调用的嵌套生成器.当我运行这个函数时,它似乎只是循环内部for循环而不再实际调用自己.我认为生成器会在必要时在递归孔之前,直到它达到yield语句.有什么线索发生了什么？

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语句

它会很好地递归,但是为了让yielded值向外传播,你需要明确地做 - 就像它是a一样return,你需要明确地return表示每次递归的结果.所以,而不是:

 self.get_next_probe(new_list, probes, unit_length)

你会做的事情如下:

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

或者,如果您使用的是Python 3.3或更高版本,您也可以这样做:

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