Permutation Python en utilisant le retour arrière

Question

J'essaie juste d'apprendre la permutation en utilisant le retour arrière. J'ai écrit le code suivant mais il s'arrête après la première sortie.

def permutations(str_in, soFar): 

    if len(str_in) != 0: 
     for c in str_in: 
      soFar.append(c) 
      temp_str = str_in 
      temp_str.remove(c) 
      print temp_str, soFar 
      permutations(temp_str, soFar) 
    else: 
     print soFar 

inp = "ABCD"   
str_in = list(inp) 
permutations(str_in, []) 

C'est la sortie que je reçois pour cela:

['B', 'C', 'D'] ['A'] 
['C', 'D'] ['A', 'B'] 
['D'] ['A', 'B', 'C'] 
[] ['A', 'B', 'C', 'D'] 
['A', 'B', 'C', 'D'] 

Je suis sûr que ce soit quelque chose de simple, mais je ne suis pas en mesure de comprendre quelle erreur que je fais ici.

Answer 1

Voici la méthode Geeksforgeeks, par Bhavya Jain, de permuter une chaîne. La logique manquante dans votre code est l'étape récursive sur les sous-listes et un comportement d'échange. Voici leur visualisation.

def permute(a, l, r): 
    if l==r: 
     print toString(a) 
    else: 
     for i in xrange(l,r+1): 
      a[l], a[i] = a[i], a[l] 
      permute(a, l+1, r) 
      a[l], a[i] = a[i], a[l] # backtrack 

# Driver program to test the above function 
string = "ABC" 
n = len(string) 
a = list(string) 
permute(a, 0, n-1) 

sortie

['A', 'B', 'C'] 
['A', 'C', 'B'] 
['B', 'A', 'C'] 
['B', 'C', 'A'] 
['C', 'B', 'A'] 
['C', 'A', 'B'] 

Answer 2

je réécrit à nouveau et avec quelques commandes d'impression entre je suis en mesure d'atteindre le résultat souhaité. Mais toujours pas tout à fait sûr de la façon dont ça fonctionne. Je pense que c'est principalement comment python modifie une liste avec chaque appel à la fonction. J'ai dû assigner des listes temporaires deux fois pour m'assurer que les listes d'origine ne sont pas modifiées. Quoi qu'il en soit, le code suivant fonctionne. Deuxième solution en utilisant des chaînes plutôt que des listes, comme mentionné dans mon commentaire ci-dessous.

def permute(String, SoFar): 
    #print "New Func Call: ", "SoFar: ", SoFar,"String: ", String, "\n" 
    if String != "": 
     for c in String: 
      TS = String.replace(c,"") 
      TSF = SoFar+c 
      permute(TS, TSF) 
      #print "A Call Finished", "SoFar: ", SoFar,"String: ", String, "TSF: ", TSF, "TS: ", TS 
    else: 
     print SoFar 

permute("ABC","")