遞歸和追加到列表

Question

我遇到了一個程序問題，程序需要一個單詞，並且一次更改一個字母，將該單詞轉換爲目標單詞。雖然，請記住，根據我給出的單詞字典，轉換後的單詞必須是合法的單詞。

我很難弄清楚如何使它遞歸。該程序對其必須採取的步驟數量有限制。

輸出需要是一個列表。所以如果函數轉換的參數是
轉換（「find」，「lose」），輸出應該是： ['find'，'fine'，'line'，'lone'，'lose']。

與我當前的代碼：

def changeling(word,target,steps): 
holderlist=[] 
i=0 
if steps<0 and word!=target: 
    return None 

if steps!=-1: 
    for items in wordList: 
     if len(items)==len(word): 
      i=0 

      if items!=word: 
       for length in items: 

        if i==1: 
         if items[1]==target[1] and items[0]==word[0] and items[2:]==word[2:]: 
          if items==target: 
           print "Target Achieved" 
           holder.list.append(target) 
          holderlist.append(items) 
          holderlist.append(changeling(items,target,steps-1)) 


        elif i>0 and i<len(word)-1 and i!=1: 
         if items[i]==target[i] and items[0:i]==word[0:i] and items[i+1:]==word[i+1:]: 
          if items==target: 
           print "Target Achieved" 
          holderlist.append(items) 
          holderlist.append(changeling(items,target,steps-1)) 


        elif i==0: 
         if items[0]==target[0] and items[1:]==word[1:]: 
          if items==target: 
           print "Target Achieved" 
          holderlist.append(items) 
          holderlist.append(changeling(items,target,steps-1)) 


        elif i==len(word)-1: 
         if items[len(word)-1]==target[len(word)-1] and items[0:len(word)-1]==word[0:len(word)-1]: 
          if items==target: 
           print "Target Achieved" 
          holderlist.append(items) 
          holderlist.append(changeling(items,target,steps-1)) 

        else: 
         return None 

        i+=1 

return holderlist 

我收到一個混亂的輸出： [ '精'，[ '線'，[ '孤獨'，[ '失去'，[]]]]，「我喜歡'，[]]

我得到了我想要的答案，但我不知道如何a）通過在列表中沒有列表來清理它。和b）喜歡出現，因爲當調用find時它會給人以美好的感覺，那麼罰款就是以目標詞爲結尾的詞，而且喜歡失敗，但我不知道如何在我追加後刪除它它的持有者名單。

任何幫助，將不勝感激。

乾杯。

Answer 1

我不完全相信，使用的extend代替append將解決所有的問題，因爲它似乎是可能沒有考慮作出改變不會導致解決的話，需要回溯。

如果事實證明我是正確的，其他的答案最終不會工作，這裏是一個遞歸函數，將您當前的結果轉換成您所尋找的：

def flatten_result(nested_list, target): 
    if not nested_list: 
     return None 
    for word, children in zip(nested_list[::2], nested_list[1::2]): 
     if word == target: 
      return [word] 
     children_result = flatten_result(children, target) 
     if children_result: 
      return [word] + children_result 
    return None 

>>> result = ['fine', ['line', ['lone', ['lose', []]]], 'fond', []] 
>>> flatten_result(result, 'lose') 
['fine', 'line', 'lone', 'lose'] 

Answer 2

如果您要將列表添加到列表中，您可能需要extend而不是append。

http://docs.python.org/library/stdtypes.html#mutable-sequence-types

Answer 3

這裏有一個替代實現。它不使用遞歸，而是使用排列。它被重寫爲通過單詞列表而不是依賴全局單詞列表，這應該使其更具可移植性。此實現嚴格依賴於發電，也可確保更小的內存佔用比（以伸展/附加解決方案）擴展列表

import itertools 

somelists = [['find','fine','line','lone','lose'], 
      ['bank','hank','hark','lark','lurk'], 
      ['tank','sank','sink','sing','ding']] 

def changeling(word, target, wordlist): 
    def difference(word, target): 
     return len([i for i in xrange(len(word)) if word[i] != target[i]]) 

    for length in xrange(1, len(wordlist) + 1): 
     for possibilities in [j for j in itertools.permutations(wordlist, length) if j[0] is word and j[-1] is target]: 
      #computes all permutations and discards those whose initial word and target word don't match parameters 
      if all(difference(possibilities[i], possibilities[i+1]) == 1 for i in xrange(0, len(possibilities) - 1)): 
       #checks that all words are exactly one character different from previous link 
       return possibilities 
       #returns first result that is valid; this can be changed to yield if you wish to have all results 

for w in somelists: 
    print "from '%s' to '%s' using only %s" % (w[-2], w[0], w) 
    print changeling(w[-2], w[0], w) 
    print 

w[-2], w[0]可以修改/替換匹配任何話，你選擇