Pythonでの再帰を使用した文字列のすべての置換

Question

私は、再帰を使って与えられた文字列のすべての置換のリストを返す以下のPythonコードを持っています。私はコードの作業を理解するために最善を尽くしたが、失敗した。誰も私に以下に述べるコードの内訳を教えてもらえますか？

def permute(s): 
    out = [] 

    # Base Case 
    if len(s) == 1: 
     out = [s] 

    else: 
     # For every letter in string 
     for i, let in enumerate(s): 
      for perm in permute(s[:i] + s[i+1:]): 
       # Add it to output 
       out += [let + perm] 
    return out 

permute('abc') 
['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] 

Answer 1

文字列の長さが1の場合、置換のみが行われるため、この場合はその文字列のみを返します。

しかし、それ以上の文字がある場合は、文字列内のすべての文字を通過します。その繰り返しの中でoutに追加される順列の最初の文字として扱われます。その後、文字列の残りのすべての順列を通り、それぞれoutに追加され、letが最初の文字になります。

しかし、permute('aab')は['aab', 'aba', 'baa']を生成しません。各エントリは返されたリストに2回置かれます。

これを回避するには、代わりにセットを使用します。したがって、out = [],out = [s]およびout.append(let + perm)の代わりに、out = set(),out = {s}およびout.add(let + perm)があります。