[算法][递归/回溯]递归实现排列型枚举
递归实现排列型枚举把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1 ≤ n ≤ 9
输入样例：
3输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1解题思路
思路一
递归回溯法
n = int(input())
status = *(n+1) # 1-n表述存储了哪些数
used = * (n+1) #用于全排列的元素是否用过
def dfs(u):
if u > n: # 全选之后 进行输出
for i in status:
print(i, end=" ")
print()
return
for i in range(1, n+1):
if used == 0: # 如果该位没有被选择
status = i # 记录下选中的是什么数字
used = 1 # 该位已选，下次不会重复选中
dfs(u+1)
status = 0 # 只有全选之后才会执行这行代码，所以需要归零
used = 0
dfs(1)递归树
ROOT (dfs(1), 已用数字: [], 剩余: )
│
├─ 分支1: 选择1 → dfs(2) (已用数字: , 剩余: )
││
│├─ 分支2: 选择2 → dfs(3) (已用数字: , 剩余: )
│││
││└─ 分支3: 选择3 → dfs(4) → 输出 ↲
││
│└─ 分支2: 选择3 → dfs(3) (已用数字: , 剩余: )
│ │
│ └─ 分支3: 选择2 → dfs(4) → 输出 ↲
│
├─ 分支2: 选择2 → dfs(2) (已用数字: , 剩余: )
││
│├─ 分支1: 选择1 → dfs(3) (已用数字: , 剩余: )
│││
││└─ 分支3: 选择3 → dfs(4) → 输出 ↲
││
│└─ 分支3: 选择3 → dfs(3) (已用数字: , 剩余: )
│ │
│ └─ 分支1: 选择1 → dfs(4) → 输出 ↲
│
└─ 分支3: 选择3 → dfs(2) (已用数字: , 剩余: )
│
├─ 分支1: 选择1 → dfs(3) (已用数字: , 剩余: )
││
│└─ 分支2: 选择2 → dfs(4) → 输出 ↲
│
└─ 分支2: 选择2 → dfs(3) (已用数字: , 剩余: )
│
└─ 分支1: 选择1 → dfs(4) → 输出 ↲思路二
字典序生成法
假设当前排列为 nums，生成下一个排列的规则如下：
[*]从右向左找第一个升序对
找到最大的索引 i，使得 nums < nums。如果找不到，说明当前排列已是最大字典序，结束循环。
[*]从右向左找第一个比 nums 大的数
找到最大的索引 j，使得 nums > nums。
[*]交换 nums 和 nums
此时，nums 是降序排列的。
[*]反转 nums
将 nums 反转，使其变为升序，得到下一个排列。
示例：n=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 → 结束代码实现
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 if i == -1: break# 已是最大排列，结束 # 步骤2：从右向左找第一个比 nums 大的数 (j) j = n - 1 while nums
页:
[1]