Python递归实现数组全排列代码错误问题排查

你的递归实现思路本身逻辑是通顺的，错误出在两个Python列表操作的细节上：

• 第一个错误：list.insert()是原地修改列表的方法，没有返回值（执行后返回None）。你当前代码把insert()的返回结果赋值给permutation再追加到结果列表，最后得到的只会是一堆None，完全不会存储实际的排列内容。
• 第二个错误：Python中列表是可变对象，你直接在递归返回的子排列上调用insert，会直接修改原有子排列的内容。同一个子排列被反复插入、篡改，后续循环拿到的就不是初始的正确子排列，插入位置的计算逻辑会完全混乱。

插入元素时不要直接修改原子排列，先拷贝一份子排列副本，在副本上执行插入操作，再把副本加入结果集即可，修正后的可运行代码如下：

def get_permutations(array):
    # 基准条件
    if len(array) <= 1:
        return [array]

    all_chars_except_last = array[:-1]
    last_char = array[-1]

    permutations_of_all_char_except_last = get_permutations(all_chars_except_last)

    permutations = []
    for sub_perm in permutations_of_all_char_except_last:
        # 遍历所有可插入位置
        for position in range(len(sub_perm) + 1):
            # 拷贝原子排列，避免修改递归返回的原始结果
            current_perm = sub_perm.copy()
            current_perm.insert(position, last_char)
            permutations.append(current_perm)
    return permutations

传入输入[1,2,3]调用上述函数，即可得到完整的全排列结果：
[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]
注：输出排列的顺序和你给出的示例顺序有差异，是插入位置的遍历顺序导致的，所有排列结果无遗漏、无重复，符合全排列的要求。

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