請解釋這種算法得到一個字符串

下面的代碼生成的字符串的所有排列的所有排列：請解釋這種算法得到一個字符串

def permutations(word): 
    if len(word)<=1: 
     return [word] 

    #get all permutations of length N-1 
    perms=permutations(word[1:]) 
    char=word[0] 
    result=[] 
    #iterate over all permutations of length N-1 
    for perm in perms: 
     #insert the character into every possible location 
     for i in range(len(perm)+1): 
      result.append(perm[:i] + char + perm[i:]) 
    return result

你能解釋它是如何工作的？我不明白遞歸。

來源

2012-12-23 gran_profaci

它看起來就像你在這裏有一個壓痕錯誤，另外，值得指出的是，這個代碼重新發明了車輪。標準庫中已經有'itertools.permutations' :-) - 雖然這並不能幫助你理解這段代碼。 – mgilson

「他」和「這個人」是什麼意思？ –

@DavidRobinson我認爲這只是一種「可愛」的方式來詢問代碼中發生了什麼。我已經重寫了這個問題，直接要求解釋，我認爲這是提問者想要的（並已收到）。 – Blckknght

的算法是：

刪除第一個字母
查找其餘字母的所有排列（遞歸步驟）
重新插入在每一個可能的位置移除信。

遞歸的基本情況是單個字母。只有一種方法可以排列單個字母。

樣例

想象開始的字是bar。

首先刪除b。
找到ar的permuatations。這給出ar和ra。
對於每個這樣的話，就把b在每一個位置：
- ar - >bar，abr，arb
- ra - >bra，rba，rab

來源

2012-12-23 04:11:32

我已經寫出了長度爲2的字符串和長度爲3以下的字符串。

排列（ 'AB'）

len('ab') is not <= 1 
perms = permutations of 'b' 
len('b') <= 1 so return 'b' in a list 
perms = ['b'] 
char = 'a' 
result = [] 
for 'b' in ['b']: 
    for 0 in [0,1]: 
     result.append('' + 'a' + 'b') 
    for 1 in [0,1]: 
     result.append('b' + 'a' + '') 
result = ['ab', 'ba']

排列（ 'ABC'）

len('abc') is not <= 1 
perms = permutations('bc') 
perms = ['bc','cb'] 
char = 'a' 
result =[] 
for 'bc' in ['bc','cb']: 
    for 0 in [0,1,2]: 
     result.append('' + 'a' + 'bc') 
    for 1 in [0,1,2]: 
     result.append('b' + 'a' + 'c') 
    for 2 in [0,1,2]: 
     result.append('bc' + 'a' + '') 
for 'cb' in ['bc','cb']: 
    for 0 in [0,1,2]: 
     result.append('' + 'a' + 'cb') 
    for 1 in [0,1,2]: 
     result.append('c' + 'a' + 'b') 
    for 2 in [0,1,2]: 
     result.append('cb' + 'a' + '') 
result = ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']

來源

2014-07-22 05:30:19 tbradley22

請解釋這種算法得到一個字符串

回答

相關問題