[算法][递归/回溯]递归实现排列型枚举

递归实现排列型枚举

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式

一个整数 n。
输出格式

按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围

1 ≤ n ≤ 9
输入样例：

1. 3

复制代码

输出样例：

1. 1 2 3
2. 1 3 2
3. 2 1 3
4. 2 3 1
5. 3 1 2
6. 3 2 1

复制代码

解题思路
思路一
递归回溯法

1. n = int(input())
2. status = [0]  *(n+1) # 1-n表述存储了哪些数
3. used = [0] * (n+1) #用于全排列的元素是否用过
4. def dfs(u):
5.     if u > n: # 全选之后 进行输出
6.         for i in status[1:]:
7.             print(i, end=" ")
8.         print()
9.         return
11.     for i in range(1, n+1):
12.         if used[i] == 0: # 如果该位没有被选择
13.             status[u] = i # 记录下选中的是什么数字
14.             used[i] = 1 # 该位已选，下次不会重复选中
16.             dfs(u+1)
18.             status[u] = 0 # 只有全选之后才会执行这行代码，所以需要归零
19.             used[i] = 0
21. dfs(1)

复制代码

递归树

1. ROOT (dfs(1), 已用数字: [], 剩余: [1,2,3])
2. │
3. ├─ 分支1: 选择1 → dfs(2) (已用数字: [1], 剩余: [2,3])
4. │  │
5. │  ├─ 分支2: 选择2 → dfs(3) (已用数字: [1,2], 剩余: [3])
6. │  │  │
7. │  │  └─ 分支3: 选择3 → dfs(4) → 输出 [1,2,3] ↲
8. │  │
9. │  └─ 分支2: 选择3 → dfs(3) (已用数字: [1,3], 剩余: [2])
10. │     │
11. │     └─ 分支3: 选择2 → dfs(4) → 输出 [1,3,2] ↲
12. │
13. ├─ 分支2: 选择2 → dfs(2) (已用数字: [2], 剩余: [1,3])
14. │  │
15. │  ├─ 分支1: 选择1 → dfs(3) (已用数字: [2,1], 剩余: [3])
16. │  │  │
17. │  │  └─ 分支3: 选择3 → dfs(4) → 输出 [2,1,3] ↲
18. │  │
19. │  └─ 分支3: 选择3 → dfs(3) (已用数字: [2,3], 剩余: [1])
20. │     │
21. │     └─ 分支1: 选择1 → dfs(4) → 输出 [2,3,1] ↲
22. │
23. └─ 分支3: 选择3 → dfs(2) (已用数字: [3], 剩余: [1,2])
24.    │
25.    ├─ 分支1: 选择1 → dfs(3) (已用数字: [3,1], 剩余: [2])
26.    │  │
27.    │  └─ 分支2: 选择2 → dfs(4) → 输出 [3,1,2] ↲
28.    │
29.    └─ 分支2: 选择2 → dfs(3) (已用数字: [3,2], 剩余: [1])
30.       │
31.       └─ 分支1: 选择1 → dfs(4) → 输出 [3,2,1] ↲

复制代码

思路二
字典序生成法
假设当前排列为 nums，生成下一个排列的规则如下：

• 从右向左找第一个升序对
  找到最大的索引 i，使得 nums < nums[i+1]。如果找不到，说明当前排列已是最大字典序，结束循环。
  
• 从右向左找第一个比 nums 大的数
  找到最大的索引 j，使得 nums[j] > nums。
  
• 交换 nums 和 nums[j]
  此时，nums[i+1:] 是降序排列的。
  
• 反转 nums[i+1:]
  将 nums[i+1:] 反转，使其变为升序，得到下一个排列。
  

示例：n=3 的生成过程
初始排列为 [1,2,3]，后续步骤如下：
当前排列找 i（升序对）找 j（比 nums 大）交换后反转 i+1 后下一个排列1 2 3i=1 (2 < 3)j=2 (3 > 2)1 3 2不反转1 3 21 3 2i=0 (1 < 3)j=1 (3 > 1)3 1 2反转 1→2 →2 12 1 32 1 3i=1 (1 < 3)j=2 (3 > 1)2 3 1反转 3→1 →1 32 3 12 3 1i=0 (2 < 3)j=2 (1 > 2 不成立) → j=13 2 1反转 2→1 →1 23 1 23 1 2i=1 (1 < 2)j=2 (2 > 1)3 2 1反转 2→1 →1 23 2 13 2 1找不到 i → 结束代码实现
[code]n = int(input())nums = list(range(1, n + 1))  # 初始排列是升序while True:    print(' '.join(map(str, nums)))    # 步骤1：从右向左找第一个升序对 (i)    i = n - 2    while i >= 0 and nums >= nums[i + 1]:        i -= 1    if i == -1:        break  # 已是最大排列，结束    # 步骤2：从右向左找第一个比 nums 大的数 (j)    j = n - 1    while nums[j]