具有yield的递归函数不返回任何内容

Question

我正在尝试创建用于置换目的的生成器。我知道还有其他方法可以在Python中执行此操作，但这是其他方法。不幸的是，我无法产生这些价值。你能帮忙吗？

def perm(s,p=0,ii=0):
    l=len(s)
    s=list(s)
    if(l==1):       
        print ''.join(s)
    elif((l-p)==2):
        yield ''.join(s)
        yield ''.join([''.join(s[:-2]),s[-1],s[-2]])
    else:
        for i in range(p,l):
            tmp=s[p]
            s[p]=s[i]
            s[i]=tmp        
            perm(s,p+1,ii)

Answer 1

您的第perm(s,p+1,ii)行实际上什么也没做：就像在键入

>>> perm("fred")
<generator object perm at 0xb72b9cd4>

但是，如果您从该通话中屈服，则是

        for subperm in perm(s, p+1, ii):
            yield subperm

那么你会得到

>>> list(perm("abc"))
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
>>> list(perm("abcd"))
['abcd', 'abdc', 'acbd', 'acdb', 'adbc', 'adcb', 'bacd', 'badc', 'bcad', 'bcda', 'bdac', 'bdca', 'cabd', 'cadb', 'cbad', 'cbda', 'cdab', 'cdba', 'dabc', 'dacb', 'dbac', 'dbca', 'dcab', 'dcba']

>>> len(_)
24
>>> len(set(perm("abcd")))
24

看起来不错。除此之外，我还没有测试过代码。

顺便说一句，您可以将s[i]和s[p]交换为s[i], s[p] = s[p], s[i]；不需要tmp变量。

PS：现在您不处理一个字符的情况。

Answer 2

在生成器中，任何时候您想返回一个值都必须到yield。就像您有一个如下所示的递归阶乘函数：

>>> def fact(n, result=1):
    if n==0: return result
    fact(n-1, result*n)

然后您想知道为什么它不返回任何内容：

>>> fact(5)
>>>

原因是该函数被递归调用，但是该值丢失了。您将要执行以下操作：

>>> def fact(n, result=1):
    if n==0: return result
    return fact(n-1, result*n)

>>> fact(5)
120

类似地，在算法的递归部分中，您执行：

    for i in range(p,l):
        tmp=s[p]
        s[p]=s[i]
        s[i]=tmp        
        perm(s,p+1,ii)

但是，这什么都没有yield，因此perm(s,p+1,ii)调用中的任何值都不会返回（编辑：实际上，它们甚至都不会被计算出）。您需要遍历递归调用的结果，然后依次返回每个结果：

    for i in range(p,l):
        tmp=s[p]
        s[p]=s[i]
        s[i]=tmp        
        for result in perm(s,p+1,ii):
            yield result