Python中yield与递归结合时输出矛盾的原因探究

尝试用Python生成器结合递归实现全排列时，发现直接通过print遍历生成器的输出，与使用list()、生成器表达式、自定义生成器包装等方式的输出不一致，具体代码及运行输出如下：

def gen_perms(seq):
    seq_len = len(seq)
    def swap(i,j):
        x = seq[i]
        seq[i] = seq[j]
        seq[j] = x
    def perms(n):
        if n == seq_len - 1:
            yield seq
        for i in range(seq_len - n):
            swap(n, n + i)
            yield from perms(n + 1)
            swap(n, n + i)
    yield from perms(0)

print('output1:')
for i in gen_perms([1,2,3]):
    print(i, end=', ')
print('')
print('output2:')
print('list(perm):', list(gen_perms([1,2,3])))

print('output3:')
it2 = (p for p in gen_perms([1,2,3]))
print(it2)
print(list(it2))

print('output4:')
def it3():
    for p in gen_perms([1,2,3]):
        yield p
print(list(it3()))

运行输出：

output1:
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], 
output2:
list(perm): [[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
output3:
<generator object <genexpr> at 0x0000021E895EB3C0>
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
output4:
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

原因分析 #

核心问题在于你始终在yield同一个列表对象，而列表是Python中的可变类型：

• 直接用print遍历时，每次yield后立刻打印当前列表的状态，此时后续的swap操作还没执行，所以能看到正确的排列结果。
• 当使用list()、生成器表达式或自定义包装生成器时，是先把所有yield的结果收集到一个列表中。但这些结果都是同一个列表的引用，生成器完成所有迭代后，列表已经被最后的swap操作还原成初始状态[1,2,3]，所以最终列表里的所有元素看起来都一样。

修复方案 #

不要直接yield原列表，而是yield它的副本，这样每个生成的排列都是独立的对象。修改perms函数中的yield seq为yield seq.copy()（或yield list(seq)）：

def gen_perms(seq):
    seq_len = len(seq)
    def swap(i,j):
        x = seq[i]
        seq[i] = seq[j]
        seq[j] = x
    def perms(n):
        if n == seq_len - 1:
            yield seq.copy()  # 改为yield副本
        for i in range(seq_len - n):
            swap(n, n + i)
            yield from perms(n + 1)
            swap(n, n + i)
    yield from perms(0)

修改后运行所有输出都会一致，得到正确的全排列列表：

output1:
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], 
output2:
list(perm): [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
output3:
<generator object <genexpr> at 0x0000021E895EB3C0>
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
output4:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

内容的提问来源于stack exchange，提问作者Blandying