Python中的递归生成器 [英] Recursive Generators in Python

问题描述

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

I wrote a function to return a generator containing every unique combination of sub-strings a given length that contain more than n elements from a primary string.

作为说明:

如果我有'abcdefghi'和一个长度为2的探针，并且我希望获得每个列表4个元素的阈值:

if i have 'abcdefghi' and a probe of length of two, and a threshold of 4 elements per list i'd like to get:

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

我第一次尝试解决此问题涉及返回列表列表.最终导致计算机内存溢出.作为粗略的辅助解决方案，我创建了一个执行类似操作的生成器.问题是我创建了一个嵌套的生成器，该生成器会自我调用.当我运行此函数时，它似乎只是在内部for循环中循环，而无需再次调用自身.我认为，生成器会在必要时先行到达递归孔，直到到达yield语句为止.有什么线索吗?

My first attempt at this problem involved returning a list of lists. This ended up overflowing the memory of the computer. As a crude secondary solution, I created a generator that does something similar. The problem is that I created a nested generator that calls itself. When I run this function, it seems to just loop around the inner for loop without actually calling itself again. I thought that a generator would precede as far down the recursion hole as necessary until it hit the yield statement. Any clue what is happening?

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重叠的元素的列表，效率会高得多...但这对我来说要容易得多.任何算法的输入仍将不胜感激.

If yield is changed to print this works just fine! I'd appreciate any help I could get. I realize this isn't an optimal implementation of this type of search problem, it seems like returning a list of found positions from the last call of get_next_probe and filtering this list for the elements that do not overlap new_last_probe.end would be far more efficient... but this was a lot easier for me to write. Any algorithm input would still be appreciated.

谢谢！

推荐答案

我认为，生成器会在必要时先行到达递归孔，直到达到yield语句为止

I thought that a generator would precede as far down the recursion hole as necessary until it hit the yield statement

它将很好地递归，但是要获得yield ed的值向外传播，您需要显式地进行操作-就像它是return一样，您需要显式地return的结果每次递归.因此，代替:

It will recurse fine, but to get the yielded value to propogate back outward, you need to do it explicitly - just like if it was a return, you would need to explicitly return the result of each recursion. So, instead of:

 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或更高版本，也可以执行以下操作:

Or if you're using Python 3.3 or newer, you can also do this:

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

这篇关于Python中的递归生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！