Explication du programme de permutation récursive Python

Question

J'ai un code qui utilise la récursivité pour calculer la permutation des caractères d'une chaîne. Je comprends la récursivité de la queue normale et les récursions pour palindrome, factorielle, conversion décimale en binaire mais j'ai du mal à comprendre comment fonctionne cette récursivité, je veux dire comment ça fonctionne en arrière-plan, pas seulement les choses abstraites du niveau supérieur. .

ici est le code

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') 

je en train d'écrire dans un journal chaque cercle est pour chaque lettre et comment la pile correspondante apparaît

Ne pas poser des questions sur mon écriture i connaître son impressionnant (sarcasme)

voici la capture d'écran de sortie

Je veux comprendre le Nitty Gritty sur la façon dont cela fonctionne en arrière-plan, mais je ne peux pas sembler comprendre le concept, très très grâce à l'avance.

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 

Le principe est assez simple. Une chaîne d'un caractère (ligne 3) n'a qu'une seule permutation, représentée par une liste contenant ce caractère (ligne 4). Les permutations de chaînes plus longues sont générées en prenant chaque caractère dans la chaîne et en permutant les caractères restants - une approche récursive et conquérante assez classique.

Pour des problèmes comme celui-ci, le site Python Tutor peut être utile pour visualiser l'exécution de votre code. Le lien que j'ai fourni est préchargé avec le code ci-dessus, et vous pouvez avancer et reculer dans le code jusqu'à ce que vous compreniez comment cela fonctionne.