在python中产生递归函数

我想创建一个用于排列目的的生成器。我知道还有其他方法可以在python中执行该操作。但这是另外一种方法。但我无法产生价值。你能帮忙吗？在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]]) 
     #print ''.join(s) 
     #print ''.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)

来源

2012-08-28 bibeesh

而不是'''.join（[''。join（s [： - 2]），s [ -1]，s [-2]]）'，你可以做'''.join（s [： - 2] + [s [-1]，s [-2]]）'或者稍微不太明显的' ''.join（s [： - 2] + s [： - 3：-1]）'（从末尾向后切片，但不包括末尾的第三个字符）。 – Dougal

你行perm(s,p+1,ii)没有做任何事情，真的：它就像打字

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

如果从调用yield，虽然，即

 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：现在你不处理一个字符的情况。

来源

2012-08-28 19:03:16 DSM

OP使用Python 2从'print'语句判断，但仍然在发布候选Python 3.3'从perm（s，p + 1，ii）'产出'也会这样做。 :) – Dougal

是的，这很漂亮。：^） – DSM

在发电机中，任何时候你想返回一个值，你必须输入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

来源

2012-08-28 19:13:49 Claudiu

值得指出的是，实际上，甚至不会计算'perm（s，p + 1，ii）'的值。 – Dougal

的确，我在最初的答案中已经提到过，但决定不包括它......将编辑 – Claudiu

在python中产生递归函数

回答

相关问题