python - 为什么不能在递归函数中使用 yield

Question

我正在使用递归来获取列表的排列。这是我写的，但是 yield 版本不起作用:

def test_permutation_rec():
    print "test 2"
    permutation_rec2([1,2,3],[])     
    print "test 1"
    for one in permutation_rec1([1,2,3],[]):
        print "one:",one 

def permutation_rec1(onelist,prelist):  
    if onelist == [] :
        print prelist
        yield prelist

    lenlist= len(onelist)
    for i, oneitem in enumerate(onelist) :
        leftlist = [onelist[j] for j in range(0,lenlist) if j != i]
        permutation_rec1(leftlist,prelist + [oneitem])

def permutation_rec2(onelist,prelist):
    if onelist == [] :
        print prelist

    lenlist= len(onelist)
    for i, oneitem in enumerate(onelist) :
        leftlist = [onelist[j] for j in range(0,lenlist) if j != i]
        permutation_rec2(leftlist,prelist + [oneitem])

if __name__ == "__main__":
    test_permutation_rec()

结果:

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

我想我在 this the answer 中使用了 yield .

谁能告诉我为什么 yield 没有生效？

顺便说一下，leftlist = [onelist[j] for j in range(0,lenlist) if j != i] 在 permutation_rec2 中，我觉得很丑。当列表很大时，它会创建许多临时列表。我该如何改进？

Answer 1

需要传递递归调用的结果；每次调用都会返回一个生成器，您必须对其进行迭代。您链接到的答案当然也会循环递归调用。

在 permutation_rec1() 上添加一个 for 循环并将每个结果值产生给下一个调用者:

def permutation_rec1(onelist, prelist):  
    if not onelist:
        yield prelist

    lenlist = len(onelist)
    for i, oneitem in enumerate(onelist):
        leftlist = [onelist[j] for j in range(lenlist) if j != i]
        for res in permutation_rec1(leftlist, prelist + [oneitem]):
            yield res

如果您使用的是 Python 3.3 或更新版本，则可以使用新的 yield from generator delegation syntax :

def permutation_rec1(onelist,prelist):  
    if not onelist:
        yield prelist

    lenlist = len(onelist)
    for i, oneitem in enumerate(onelist):
        leftlist = [onelist[j] for j in range(lenlist) if j != i]
        yield from permutation_rec1(leftlist, prelist + [oneitem])