рекурсия перестановка строки сбой

Question

Я пишу код «рекурсивная перестановка строки» в Python Он разбился после одного цикла дерева (?). Я не могу найти причину. объясните пожалуйста.

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

После того, как формируется память [CB, BC] он должен идет к следующему за цикл. , но это просто конец.

Answer 1

Я думаю, что вы должны забыть 'еще' в вашем состоянии:

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

Вы можете исправить вашу функцию следующим образом:

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 

или использовать стандартную функцию библиотеки itertools.permutations:

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

оба из них возвращают одинаковый результат:

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