Python 全排列算法：生成 1 到 n 的所有不重复排列

问题描述：

输出自然数 1 到 n 的所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复数字。

输入格式：

1 <= n <= 9

输出格式：

由 1 到 n 组成的所有不重复的数字序列。每行一个序列

输入样例：

输出样例：

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

算法思路：

这道题是全排列问题，可以使用回溯算法进行求解。我们可以从 1 开始向 n 递归，递归过程中需要维护一个布尔数组 used，表示哪些数字已经被使用过。如果当前数字没有被使用，则将其加入到当前排列中，然后继续递归下一位数字。递归完后需要回溯，将当前数字从排列中删除，并将其设置为未使用过，然后继续尝试下一个数字。

同时，为了避免重复，我们可以在递归过程中判断当前数字是否已经被使用过，如果已经被使用过，则跳过该数字。

Python 代码：

def permutation(n):
    '''
    生成 1 到 n 的所有不重复排列

    Args:
        n: 自然数 n

    Returns:
        一个包含所有不重复排列的列表
    '''
    used = [False] * (n + 1)
    res = []
    path = []

    def backtrack(index):
        if index == n + 1:
            res.append(path.copy())
            return

        for i in range(1, n + 1):
            if not used[i]:
                used[i] = True
                path.append(i)
                backtrack(index + 1)
                path.pop()
                used[i] = False

    backtrack(1)
    return res

# 输入 n
n = int(input())

# 生成所有排列
permutations = permutation(n)

# 输出结果
for permutation in permutations:
    print(' '.join(map(str, permutation)))

代码解析：

permutation(n) 函数：
- 初始化 used 列表，用于标记数字是否被使用过。
- 初始化 res 列表，用于存储所有不重复排列。
- 初始化 path 列表，用于存储当前排列。
- 调用 backtrack(1) 函数开始递归。
backtrack(index) 函数：
- 如果 index 等于 n + 1，说明已经遍历完所有数字，将当前 path 加入到 res 中。
- 遍历 1 到 n 的所有数字：
  - 如果当前数字 i 未被使用过，则将其加入到 path 中，并将 used[i] 设置为 True，表示该数字已经被使用过。
  - 递归调用 backtrack(index + 1)，继续尝试下一个数字。
  - 回溯：将当前数字 i 从 path 中删除，并将 used[i] 设置为 False，表示该数字可以被再次使用。
主函数部分：
- 输入数字 n。
- 调用 permutation(n) 函数生成所有排列。
- 遍历所有排列，并将其打印出来。

总结：

本文介绍了使用 Python 实现全排列算法的代码示例，并对代码进行了详细的解析。回溯算法是解决排列组合问题的常用方法，在实际应用中具有广泛的应用场景。