Rekursion Permutation Zeichenfolge Absturz

Question

Ich schreibe einen Code "Rekursionspermutation der Zeichenfolge" in Python Es stürzte nach einem Baum (?) Zyklus. Ich kann den Grund nicht finden. Bitte erläutern Sie es.

memory = [] 
memory2 = [] 

def permutation(s): 


if len(s)==1: 
    return s 


for i,char in enumerate(s): 
    returns= permutation(s[:i] + s[i+1:]) 
    print(returns) 
    if returns == None: 
     for j in memory: 
      memory2.append(s[i] + j) 
     memory = [] 
    memory.append(s[i] + returns) 
    print(memory) 
s = "ABC" 
print(permutation(s)) 

Nachdem er den Speicher gebildet [cb, bc] Es sollte für Schleife zum nächsten geht. aber es endet einfach.

Answer 1

Ich glaube, Sie haben vergessen 'else' in Ihrem Zustand:

memory = [] 
memory2 = [] 

def permutation(s): 
    global memory 
    global memory2 

    if len(s)==1: 
     return s 

    for i, char in enumerate(s): 
     returns = permutation(s[:i] + s[i+1:]) 

     if returns == None: 
      for j in memory: 
       memory2.append(s[i] + j) 
      memory = [] 
     else: # <--- here 
      memory.append(s[i] + returns) 

s = "ABC" 
permutation(s) 
print(memory2) 

Answer 2

Sie Ihre Funktion wie so korrigieren:

def permutations(s): 
    if len(s) <= 1: 
     return [s] 
    result = [] 
    for i, letter in enumerate(s): 
     for perm in permutations(s[:i] + s[i + 1:]): 
      result.append(letter + perm) 
    return result 

oder verwenden Standard-Library-Funktion itertools.permutations:

from itertools import permutations 
perms = ["".join(perm) for perm in permutations(s)] 

beide ergeben das gleiche Ergebnis:

s = "abc" 
print(permutations(s)) # ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']