2012-08-28 124 views
1

我想創建一個用於排列目的的生成器。我知道還有其他方法可以在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) 
+0

而不是'''.join([''。join(s [: - 2]),s [ -1],s [-2]])',你可以做'''.join(s [: - 2] + [s [-1],s [-2]])'或者稍微不太明顯的' ''.join(s [: - 2] + s [: - 3:-1])'(從末尾向後切片,但不包括末尾的第三個字符)。 – Dougal

回答

5

你行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:現在你不處理一個字符的情況。

+3

OP使用Python 2從'print'語句判斷,但仍然在發佈候選Python 3.3'從perm(s,p + 1,ii)'產出'也會這樣做。 :) – Dougal

+0

是的,這很漂亮。 :^) – DSM

0

在發電機中,任何時候你想返回一個值,你必須輸入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 
+0

值得指出的是,實際上,甚至不會計算'perm(s,p + 1,ii)'的值。 – Dougal

+0

的確,我在最初的答案中已經提到過,但決定不包括它......將編輯 – Claudiu