如何将递归函数转换为生成器？

Question

我有以下递归函数来为（命名的）位置列表生成有效配置列表，其中每个位置只能使用一次：

def generate_configurations(configurations, named_positions, current):
    if len(current) == len(named_positions):
        configurations.append(current)
        return configurations

    name, positions = named_positions[len(current)]
    for x in positions:
        if x not in current:
            generate_configurations(configurations, named_positions, current + (x,))

    return configurations

这是我如何称呼它的一个例子：

named_positions = [('a', [0,1,2]),
                   ('b', [1,3]),
                   ('c', [1,2])]

for comb in generate_configurations([], named_positions, ()):
    print comb

给出以下输出：

(0, 1, 2)
(0, 3, 1)
(0, 3, 2)
(1, 3, 2)
(2, 3, 1)

此外，可能存在没有个有效组合，例如named_positions = [('a', [3]), ('b', [3])].

现在，根据输入 named_positions，configurations 列表会很快变大，从而导致 MemoryError。我相信这个函数可以重写为生成器，所以我尝试了以下操作：

def generate_configurations(named_positions, current):
    if len(current) == len(named_positions):
        yield current

    name, positions = named_positions[len(current)]
    for x in positions:
        if x not in current:
            generate_configurations(named_positions, current + (x,))

named_positions = [('a', [0,1,2]),
                   ('b', [1,3]),
                   ('c', [1,2])]

for comb in generate_configurations(named_positions, ()):
    print comb

但这根本不会产生任何结果。我做错了什么？

Answer 1

您需要 yield 向上递归调用堆栈，否则内部 yield 永远不会发生并被丢弃。由于这是标记为 Python 2.7，递归调用将通过更改处理：

if x not in current:
    # Creates the generator, but doesn't run it out to get and yield values
    generate_configurations(named_positions, current + (x,))

至：

if x not in current:
    # Actually runs the generator and yields values up the call stack
    for y in generate_configurations(named_positions, current + (x,)):
        yield y

在 Python 3.3 及更高版本中，您可以直接委托：

if x not in current:
    yield from generate_configurations(named_positions, current + (x,)):

Answer 2

当您使用生成器时，您需要确保您的子生成器递归调用传递回调用方法。

def recur_generator(n):
    yield my_thing
    yield my_other_thing
    if n > 0:
        yield from recur_generator(n-1)

请注意，yield from 是将 yield 调用传递回父调用的原因。

您应该将递归调用行更改为

yield from generate_configurations(named_positions, current + (x,))

否则，你的发电机没问题。

编辑：没注意到这是 python2。您可以使用

for x in recur_generator(n-1):
    yield x

而不是 yield from。

如何将递归函数转换为生成器？

How to convert recursive function to generator?

python

recursion

generator

python-2.7