如何用递归函数生成固定首元素的数组全排列集合？代码问题求助

需求明确：给定数组（如[1,2,3,4]），编写递归函数返回固定首元素的全排列数组，结果需类似[[1,2,3,4],[1,3,2,4],[1,4,2,3],[1,3,4,2],[1,2,4,3],[1,4,3,2]]。

原代码的核心问题 #

两段代码都存在以下致命问题：

• 全局变量导致状态混乱：arr_new和subsets_array作为全局变量，递归的不同分支会互相修改这些变量，直接引发重复排列、结果错乱。
• 无递归终止条件：函数末尾无限调用自身，会触发栈溢出，根本无法正常返回结果。
• 回溯逻辑错误：手动pop的时机和位置不对，无法正确回到上一层递归的状态。
• 结果收集时机错误：第二段代码把未完成的中间数组也加入结果，而非仅收集长度符合要求的完整排列。

正确的递归实现思路 #

固定首元素的全排列可以拆分为两步：

1. 提取原数组的首元素，作为所有结果排列的第一个元素。
2. 对剩余元素做全排列，将每个子排列拼到首元素后，得到最终结果。

递归的关键是用参数传递状态（而非全局变量），让每个递归分支的状态独立；当剩余元素为空时，说明当前排列完成，加入结果列表。

修正后的代码 #

def fixed_first_permutation(arr):
    if len(arr) <= 1:
        return [arr]
    # 固定首元素
    first_element = arr[0]
    # 待排列的剩余元素
    rest_elements = arr[1:]
    result = []

    def permute(current_subset, remaining):
        # 终止条件：剩余元素为空，当前子排列完成
        if not remaining:
            result.append([first_element] + current_subset)
            return
        # 遍历剩余元素，逐个选择并递归
        for i in range(len(remaining)):
            # 选择第i个元素加入当前子排列，剩余元素移除第i个
            permute(current_subset + [remaining[i]], remaining[:i] + remaining[i+1:])

    permute([], rest_elements)
    return result

# 测试示例
test_arr = [1,2,3,4]
print(fixed_first_permutation(test_arr))

代码说明 #

1. 外层函数处理边界情况（数组长度≤1时直接返回），并拆分首元素和剩余元素。
2. 内部递归函数permute接收两个参数：current_subset是当前已构建的子排列，remaining是待选的剩余元素。
3. 当remaining为空时，将首元素与当前子排列拼接，加入结果列表。
4. 遍历剩余元素时，通过创建新列表传递参数（current_subset + [remaining[i]]、remaining[:i] + remaining[i+1:]），自动实现回溯，无需手动修改原状态。

运行后输出结果完全符合需求：

[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2]]

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