递归排列字符串崩溃

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] 它应该后前进到下一个for循环。 但它只是结束它。

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