递归过程中的`yield`

Question

假设我有一个 Python 列表，表示某些变量的范围：

conditions = [['i', (1, 5)], ['j', (1, 2)]]

这表示变量 i 的范围从 1 到 5，在循环变量 j 的范围内从 1 到 2。我想要每个可能的组合的字典：

{'i': 1, 'j': 1}
{'i': 1, 'j': 2}
{'i': 2, 'j': 1}
{'i': 2, 'j': 2}
{'i': 3, 'j': 1}
{'i': 3, 'j': 2}
{'i': 4, 'j': 1}
{'i': 4, 'j': 2}
{'i': 5, 'j': 1}
{'i': 5, 'j': 2}

原因是我想遍历它们。但是因为整个 space 太大了，我不想生成所有它们，存储它们然后迭代那个字典列表。我考虑过使用以下递归过程，但我需要 yield 部分的一些帮助。它应该在哪里？如何避免嵌套生成器？

def iteration(conditions, currentCondition, valuedIndices):
    if currentCondition == len(conditions):
        yield valuedIndices
    else:
        cond = conditions[currentCondition]
        index = cond[0]
        lim1 = cond[1][0]
        lim2 = cond[1][1]
        for ix in range(lim1, lim2 + 1):
            valuedIndices[index] = ix
            yield iteration(conditions, currentCondition + 1, valuedIndices)

现在我希望能够做到：

for valued_indices in iteration(conditions, 0, {}):
    ...

Answer 1

您或许可以通过内部生成器理解和 yield from 简化一点：

def dict_factory(i, j):
    r1 = range(1, i + 1)
    r2 = range(1, j + 1)
    dictgen = ({'i':x, 'j':y} for x in r1 for y in r2)
    yield from dictgen

用作：

foo = dict_factory(5, 2)
while True:
    print(next(foo))

Answer 2

在这种情况下，退后一步重新开始可能更容易。

让我们首先使用涉及 zip:

的众所周知的技巧将键和间隔分开

>>> keys, intervals = list(zip(*conditions))
>>> keys
('i', 'j')
>>> intervals
((1, 5), (1, 2))

（两者的对应关系保留了原来的配对；intervals[i]是变量keys[i]对所有i的区间。）

现在，让我们根据这些间隔创建适当的范围对象

>>> intervals = [range(x, y+1) for x, y in intervals]
>>> list(intervals[0])
[1, 2, 3, 4, 5]
>>> list(intervals[1])
[1, 2]

我们可以计算这些 range 个对象的乘积

>>> for v in product(*intervals):
...   print(v)
...
(1, 1)
(1, 2)
(2, 1)
(2, 2)
(3, 1)
(3, 2)
(4, 1)
(4, 2)
(5, 1)
(5, 2)

您应该将其识别为用于每个字典的值。您可以使用键压缩每个值，为 dict 命令创建一组适当的参数。例如：

>>> dict(zip(keys, (1,1)))
{'i': 1, 'j': 1}

将所有这些放在一起，我们可以迭代产品以依次产生每个 dict，产生它。

def iteration(conditions):
    keys, intervals = zip(*conditions)
    intervals = [range(x, y+1) for x, y in intervals]
    yield from (dict(zip(keys, v)) for v in product(*intervals))

Answer 3

我不确定您是否特别需要使用递归，但您可以使用 itertools 产品方法生成这些以生成所有组合。这是这样写的，你可以有 1 到 n 个条件，它应该仍然有效并且 return 你逐项。

from itertools import product


def iterations2(conditions):
    labels, ranges = list(zip(*conditions))
    ranges = [range(item[0], item[1] + 1) for item in ranges]
    for nums in product(*ranges):
        yield dict(zip(labels, nums))


conditions = [['i', (1, 5)], ['j', (1, 2)], ['z', (3, 6)]]
for valued_indices in iterations2(conditions):
    print(valued_indices)

输出

{'i': 1, 'j': 1, 'z': 3}
{'i': 1, 'j': 1, 'z': 4}
{'i': 1, 'j': 1, 'z': 5}
{'i': 1, 'j': 1, 'z': 6}
{'i': 1, 'j': 2, 'z': 3}
{'i': 1, 'j': 2, 'z': 4}
{'i': 1, 'j': 2, 'z': 5}
{'i': 1, 'j': 2, 'z': 6}
{'i': 2, 'j': 1, 'z': 3}
{'i': 2, 'j': 1, 'z': 4}
{'i': 2, 'j': 1, 'z': 5}
{'i': 2, 'j': 1, 'z': 6}
{'i': 2, 'j': 2, 'z': 3}
{'i': 2, 'j': 2, 'z': 4}
{'i': 2, 'j': 2, 'z': 5}
{'i': 2, 'j': 2, 'z': 6}
{'i': 3, 'j': 1, 'z': 3}
{'i': 3, 'j': 1, 'z': 4}
{'i': 3, 'j': 1, 'z': 5}
{'i': 3, 'j': 1, 'z': 6}
{'i': 3, 'j': 2, 'z': 3}
{'i': 3, 'j': 2, 'z': 4}
{'i': 3, 'j': 2, 'z': 5}
{'i': 3, 'j': 2, 'z': 6}
{'i': 4, 'j': 1, 'z': 3}
{'i': 4, 'j': 1, 'z': 4}
{'i': 4, 'j': 1, 'z': 5}
{'i': 4, 'j': 1, 'z': 6}
{'i': 4, 'j': 2, 'z': 3}
{'i': 4, 'j': 2, 'z': 4}
{'i': 4, 'j': 2, 'z': 5}
{'i': 4, 'j': 2, 'z': 6}
{'i': 5, 'j': 1, 'z': 3}
{'i': 5, 'j': 1, 'z': 4}
{'i': 5, 'j': 1, 'z': 5}
{'i': 5, 'j': 1, 'z': 6}
{'i': 5, 'j': 2, 'z': 3}
{'i': 5, 'j': 2, 'z': 4}
{'i': 5, 'j': 2, 'z': 5}
{'i': 5, 'j': 2, 'z': 6}

递归过程中的`yield`

`yield` inside a recursive procedure

python

recursion

yield