生成全排列：递归生成器中被yield的子序列排列为何未出现在输出？

我在CS61A作业中遇到了生成全排列的问题：需要实现生成器函数gen_perms，返回序列所有排列的生成器。我写出了对应的代码，调用后能得到预期的正确输出，但存在疑惑：代码中递归调用generator(list_seq[1:])的yield语句先执行，按道理应该先输出子序列的排列，可这些子序列排列并未出现在最终输出中。我可能对生成器的工作机制存在误解，希望有人能解释原因。

代码示例 #

def gen_perms(seq):
    def generator(seq_):
        list_seq = list(seq_)
        if len(list_seq) == 1:
            yield list_seq
        else:
            for item in generator(list_seq[1:]):
                for i in range(len(list_seq)):
                    yield item[:i] + [list_seq[0]] + item[i:]
    return generator(seq)

调用示例 #

print(list(gen_perms([1, 2, 3])))

输出结果 #

[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

核心原因是递归生成器的产出值被上层循环消费了，并没有直接传递到最终输出，具体拆解：

• 递归最底层：处理[3]时，generator([3])产出[3]，但这个值并没有直接返回给最外层，而是被上层generator([2,3])里的for item in generator([3])循环接住。
• 到generator([2,3])层：拿到item=[3]后，不会直接产出[3]，而是进入内层循环，把2插入到[3]的不同位置，产出[2,3]和[3,2]——这两个值又被更上层的generator([1,2,3])循环接住。
• 最上层generator([1,2,3])：拿到item=[2,3]和item=[3,2]后，同样不会直接产出这两个子序列排列，而是把1插入到它们的每个位置，生成最终的6个全排列并产出。

简单说，递归生成器每一层产出的中间值，都被上一层当作“原材料”加工了，只有最上层加工后的最终结果才会被传递到gen_perms的返回生成器里，所以你看不到子序列的排列出现在输出中。

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