为什么不能在递归函数中使用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

我想我在答案中使用yield了这个.

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

顺便说一句,leftlist = [onelist[j] for j in range(0,lenlist) if j != i] 在permutation_rec2,是丑陋的,我认为.当列表很大时,它会创建许多临时列表.我怎样才能改善这一点？

Answer 1

你需要传递递归调用的结果; 每个调用返回一个生成器,你必须迭代它.您链接的答案肯定会循环遍历递归调用.

添加for循环permutation_rec1()并将每个结果值生成到下一个调用者:

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生成器委派语法:

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])