两种逻辑相近的Python字符串全排列代码为何输出结果不一致？

问题核心原因 #

两段代码的本质差异是Python中不可变对象和可变对象的传参行为不同：

• 字符串是不可变对象，传递时会生成新的副本
• 列表是可变对象，传递时传递的是原对象的引用，所有递归操作修改的都是同一个列表

第一段代码逻辑说明 #

第一段代码每次递归传入的是拼接后的字符串，每次进入函数第一行都会将传入的字符串转为独立的新列表，每层递归的列表完全独立，下层递归的任何修改都不会影响上层函数的列表状态，因此不需要额外的回溯操作就能得到正确的全排列结果。

第二段代码问题分析 #

第二段代码全程传递同一个列表，所有递归层的修改都会直接修改原列表，而你没有补充回溯逻辑：
当递归调用返回后，列表已经被下层递归的交换操作修改过，不会自动恢复到当前层for循环迭代前的状态，因此下一次循环迭代时使用的是被改乱的列表，最终输出结果错误。

修复方案 #

在递归调用结束后添加回溯操作，将列表恢复到交换前的状态即可：

def permutations(msg, l, r):
    if l == r-1:
        print("".join(msg))
    else:
        for i in range(l, r):
            msg[i], msg[l] = msg[l], msg[i]
            permutations(msg, l+1, r)
            # 新增回溯：把交换的元素换回来，恢复列表状态
            msg[i], msg[l] = msg[l], msg[i]

内容的提问来源于stack exchange，提问作者Andreas Thanopoulos