9

我编写了一个函数来返回一个生成器，该生成器包含给定长度的子字符串的每个唯一组合，其中包含来自主字符串的 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 的元素会更有效率...但这对我来说写起来容易得多。任何算法输入仍然会受到赞赏。

谢谢！

4

1 回答 1

18

我认为生成器会根据需要在递归漏洞之前尽可能远，直到它遇到 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)
于 2012-04-22T02:00:03.600 回答