我怎样才能从任意深度的递归中产生？

Question

我已经编写了一个函数来创建任意长度的输入组合，因此递归似乎是实现它的明显方法。虽然对于 return 一个结果列表的小玩具示例来说是可以的，但我更愿意 yield 它们。我读过 yield from，但不完全理解它的使用方式，这些示例似乎没有涵盖我的用例，并且希望将它插入我的代码中还没有产生任何东西作品。请注意，编写此递归代码已达到我 python 能力的极限，因此有大量调试打印语句。

这是工作列表 return 代码，我希望的非工作产量已被注释掉。

def allposs(elements, output_length):
    """
    return all zero insertion paddings of elements up to output_length maintaining order

    elements -         an iterable of length >= 1
    output_length      >= len(elements)

    for instance allposs((3,1), 4) returns
    [[3,1,0,0], [3,0,1,0], [3,0,0,1], [0,3,1,0], [0,3,0,1], [0,0,3,1]]
    """

    output_list = []

    def place_nth_element(nth, start_at, output_so_far):
        # print('entering place_nth_element with nth =', nth,
        #      ', start_at =', start_at,
        #      ', output_so_far =', output_so_far)
        
        last_pos = output_length - len(elements) + nth
        # print('iterating over range',start_at, 'to', last_pos+1)
        for pos in range(start_at, last_pos+1):
            output = list(output_so_far)           
            # print('placing', elements[nth], 'at position', pos)
            output[pos] = elements[nth]

            if nth == len(elements)-1:
                # print('appending output', output)
                output_list.append(output)
                # yield output    
            else:
                # print('making recursive call')
                place_nth_element(nth+1, pos+1, output)
   
    place_nth_element(0, 0, [0]*output_length)
    return output_list

if __name__=='__main__':
    for q in allposs((3,1), 4):
        print(q)

使用 yield from 让我的列表一次生成一个组合的语法是什么？

Answer 1

递归生成器是一个强大的工具，我很高兴您正在努力研究它们。

What is the syntax to use yield from to get my list generated a combination at a time?

你把 yield from 放在表达式 from 的前面，结果应该是 yielded;在你的情况下，递归调用。因此：yield from place_nth_element(nth+1, pos+1, output)。这个想法是 from recursively-called 生成器（在幕后）迭代每个结果，并在过程中的这一点 yielded。

请注意，要使其生效：

您需要yield递归基础级别的单个结果
要从生成的生成器中“收集”结果，您需要迭代 top-level 调用的结果。幸运的是，迭代在很多地方都是 built-in；例如，您可以只调用 list 它会为您迭代。

与其将递归生成器嵌套在包装函数中，我更愿意将其编写为单独的辅助函数。由于不再需要从递归中访问output_list，因此不需要形成闭包；和 flat is better than nested 正如他们所说。然而，这确实意味着我们需要通过递归传递 elements。我们不需要传递 output_length 因为我们可以重新计算它（output_so_far 的长度在整个递归过程中是恒定的）。

此外，我发现在执行这些算法时，尽可能从功能上思考（在范式意义上——即避免副作用和可变性，并通过创建新对象继续）是有帮助的。你有一个可行的方法使用 list 来制作副本（虽然使用 .copy 方法更清楚），但我认为有一个更简洁的方法，如下所示。

所有这些建议将我们引向：

def place_nth_element(elements, nth, start_at, output_so_far):        
    last_pos = len(output_so_far) - len(elements) + nth
    for pos in range(start_at, last_pos+1):
        output = output_so_far[:pos] + (elements[nth],) + output_so_far[pos+1:]
        if nth == len(elements)-1:
            yield output    
        else:
            yield from place_nth_element(elements, nth+1, pos+1, output)


def allposs(elements, output_length):
    return list(place_nth_element(elements, 0, 0, (0,)*output_length))

但是，我不会那样解决问题 - 因为标准库已经提供了一个简洁的解决方案：我们可以找到 itertools.combinations 索引值应该放在的位置，然后插入它们。现在我们不再需要递归地思考，我们可以继续改变值:)

from itertools import combinations

def place_values(positions, values, size):
    result = [0] * size
    for position, value in zip(positions, values):
        result[position] = value
    return tuple(result)


def possibilities(values, size):
    return [
        place_values(positions, values, size)
        for positions in combinations(range(size), len(values))
    ]

我怎样才能从任意深度的递归中产生？

How can I yield from an arbitrary depth of recursion?

python

recursion

yield