Python再帰的置換プログラムの説明

Question

再帰を使用して文字列の文字の置換を計算するコードがあります。私は正常な尾の再帰と回文、階乗、小数から2進数への再帰を簡単に理解していますが、この再帰がどのように機能するかを理解する上で問題があります。 。ここ

コード

from __future__ import print_function 

def permutef(s): 
    #print('\nIM CALLED\n') 
    out = [] 

    if len(s) == 1: 
     out = [s] 
    else: 
     for i,let in enumerate(s): 

      #print('LETTER IS {} index is {}'.format(let, i)) 

      #Slicing as not including that letter but includes every letter except that to perform the permutation 

      for perm in permutef(s[:i] + s[i+1:]): 

       print(perm) 

       out += [let + perm] 
    return out 


per = permutef('abc') 

print('\n\n\n', per, '\n\n\n') 

は、私は、各円は各文字のためである紙に書いていたし、どのように対応するスタックが

をポップすることは、私の手書き私について質問しないでくださいですその素晴らしい（気難しさ）を知って

ここに出力されたスクリーンショットです

これはバックグラウンドでどのように機能するのかを理解したいと思っていますが、私はコンセプトを推測することはできません。

Answer 1

1 def permutef(s): 
2  out = [] 
3  if len(s) == 1: 
4   out = [s] 
5  else: 
6   for i,let in enumerate(s): 
7    for perm in permutef(s[:i] + s[i+1:]): 
8     print(perm) 
9     out += [let + perm] 
10  return out 

原則はかなり簡単です。 1文字の文字列（3行目）は、その文字を含むリスト（行4）で表される1つの順列のみを持ちます。長い文字列の順列は、文字列内の各文字を取り出し、残りの文字を置換することによって生成されます。これはかなり古典的な再帰的な分割と征服のアプローチです。

このような問題の場合、Python Tutorサイトはコードの実行を視覚化するのに便利です。私が提供したリンクには、上記のコードがあらかじめロードされています。コードがどのように動作するか理解するまで、コードを前後に進めることができます。