在Python中遞歸地實現排列

我很抱歉已經有很多關於這個問題的文章。但是，我很難在自己的實施中看到自己的錯誤。所以我試圖編寫一個函數，它接受一個字符串並以列表的形式返回所有可能的排列。在Python中遞歸地實現排列

理論上應該是這樣的：

allPermutations（「ABC ... Z」）= [A + allPermutations（B，C，... Z），B + allPermutations（A，C .. .z）...]

我在當前的實現中，當在字符串「Hello」上測試時，會輸出一堆重複的排列。任何人都可以幫我看看我哪裏出錯了。感謝您的協助！

這裏是代碼：

def allPermutations(strng): 
    if len(strng) ==1: 
     return [strng] 
    perm_list = [] 
    for i in strng: 
     smallerStr = strng.replace(i,"",1) 
     z = allPermutations(smallerStr) 

     for t in z: 
      perm_list.append(i+t)   
    return perm_list

來源

2013-05-15 Thalatta

我不確定你是否只是想練習，但如果你不是，itertools有一個方便的排列功能。例如， – James

，「你好」有2個「l」。因此，它會有雙重排列。 – Drakosha

你將有重複排列如果您有重複的字母，因爲這是你的邏輯做什麼。

例如，'Hello'，第l，您要添加'l' + perm爲'Helo'每個置換，然後第二l，你再次增加'l' + perm爲'Helo'每個排列。

有幾種方法可以顯示沒有重複的排列。最簡單的是隻遍歷set(strng)而不是strng：

def allPermutations(strng): 
    if len(strng) ==1: 
     return [strng] 
    perm_list = [] 
    for i in set(strng): 
     smallerStr = strng.replace(i,"",1) 
     z = allPermutations(smallerStr) 

     for t in z: 
      perm_list.append(i+t)   
    return perm_list

作爲一個側面說明，你幾乎從來沒有想要做這樣的事：

for i in strng: 
    smallerStr = strng.replace(i,"",1)

...或

for x in lst: 
    idx = lst.find(x)

除了一個明顯的性能問題，就是你不必要地搜索了某些東西你有，如果你有任何重複的元素，這是不可能的。例如，無論您嘗試更換/查找'Hello'中的第一個'l'還是第二個，它都會替換第一個。

正確的做法是使用enumerate。例如：

for idx, i in enumerate(strng): 
    smallerStr = strng[:idx] + strng[idx+1:]

在這種特殊情況下，它發生在沒有關係，因爲你不真正關心你是否要移除第一l或第二個。但是，如果你已經想好了，並且確保它是正確的，那麼你應該只依靠這一點，並且可能會添加一條評論來解釋爲什麼它是正確的。一般來說，不要這樣做。

來源

2013-05-15 23:03:09 abarnert

請，走itertools模塊中一探究竟。這將是眼前這個：

import itertools 
[ ''.join(i) for i in itertools.permutations(mystring) ]

一個例子：

[ ''.join(i) for i in itertools.permutations('abc')] 
#['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

來源

2013-05-15 22:49:57

@Drakosha謝謝！我會刪除這個，因爲實際上沒有錯誤。 – Thalatta

在Python中遞歸地實現排列

回答

相關問題