再帰的アルゴリズムは - との新しいリストを作成する対延長「+」

Question

だから私はそれらの可能性小文字のすべての組み合わせが'_'文字に置換されるまで、その下の再帰関数は、アルファベットの各小文字で'_'文字を置き換える続けています。

簡単な例：

repl_underscores('__A')

>>>[a_A,b_A,c_A......aaA,abA,acA....zzA]

私は以下のコメントが同じに変更し、言及してリストを構築するために延長での作業この機能を持っていました既存のリストをその場で繰り返して、その仕事を達成する。

実際には、同じ結果を得ることを目的として、各呼び出しで新しいリストを作成し、その結果を連続する再帰呼び出しに渡すために書き直したかったのです。

これはうまくいかず、各呼び出しで新しいリストを作成しているという事実と関係がありますが、再帰呼び出しのたびに組み立てられたバージョンを渡していたのでそれらの呼び出しに変更が通知されるのでOKです。

どこが壊れているかわかりません。私は同じリスト（変更可能なデフォルト、グローバル変数、または拡張のいずれかを介して）を変更することによって動作させることができますが、再帰するたびに新しいクリーンリストを構築したいと思います。

def repl_underscores(letters,res=None): 
    if res is None: res = list() 
    if '_' not in letters: return res 
    repl = [letters.replace('_',letter,1) for letter in string.ascii_lowercase] 
    res = res + repl #using += works, due to extending being a mutation (same list referenced at each call) 
    for each in repl: 
     repl_underscores(each,res) #trying to pass modified list to keep building up 
    return res 

print(repl_underscores('__DER')) 

Answer 1

res = res + repl #using += works, due to extending being a mutation (same list referenced at each call) 

あなたが推測しているように見えるので、この行は、問題です。再帰呼び出しでは、毎回という新しいローカルリストが割り当てられます。これは、古いものへの参照を保持しないため、呼び出し元には変更が通知されません。

幸いにもあなたの関数は、すでにリストを返します、それでは、ちょうどそれをキャプチャしてみましょう：

 res = repl_underscores(each,res) #trying to pass modified list to keep building up 

Answer 2

より良い関数の引数を修正するが、返された値（より機能的なスタイル）でビルドしないように。コードをわずかに変更するだけで、意図したとおりに動作します。

輸入列

def repl_underscores(letters): 
    res = list() 
    if '_' not in letters: return res 
    repl = [letters.replace('_',letter,1) for letter in string.ascii_lowercase] 
    res += repl 
    for each in repl: 
     res += repl_underscores(each) 
    return res 

print(repl_underscores('__DER')) 

Answer 3

ちょうど再帰なしで機能を使用します。

from itertools import combinations_with_replacement, chain 

def repl_underscores(letters): 
    result = [] 
    for chars in combinations_with_replacement(string.lowercase, letters.count('_')): 
     chars = chain(chars,['']) 
     result.append(''.join(a+next(chars) for a in letters.split('_'))) 
    return result