Recursive function with yield doesn't return a

问题:

I am trying to create a generator for permutation purpose. I know there are other ways to do that in Python but this is for something else. Unfortunately, I am not able to yield the values. Can you help?

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)

回答1:

Your line perm(s,p+1,ii) doesn't do anything, really: it's just like typing

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

If you yield from that call, though, i.e.

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

Then you'd get

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

which looks okay. I haven't tested the code beyond that.

BTW, you can swap s[i] and s[p] with s[i], s[p] = s[p], s[i]; no need for a tmp variable.

PS: right now you don't handle the one-character case.

回答2:

In a generator, any time you want to return a value you have to yield. It's like you had a recursive factorial function that looked like this:

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

And then you wonder why it doesn't return anything:

>>> fact(5)
>>>

The reason is that the function is called recursively, but the value is lost. You'll want to do:

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

>>> fact(5)
120

Analogously, in the recursive part of your algorithm you do:

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

This doesn't yield anything, though, so none of the values from the perm(s,p+1,ii) call will be returned (EDIT: actually, none of them will even be computed). You'll want to iterate through the results of the recursive call and return each one in turn:

    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