全排列问题

一、next_permutation函数（生成下一个字典序排列）

该函数接收一个排列（数组arr），返回其下一个字典序排列（比当前排列大的最小排列）；若当前是最后一个排列（完全降序），则返回None。

1. 复制输入数组（避免修改原数组）

arr = arr.copy()

• 作用：创建输入数组的副本，避免修改原始输入数组。例如，若输入是[1,2,3]，复制后操作的是新数组，原数组保持不变。

2. 寻找关键位置i（最后一个升序位置）

i = len(arr) - 2  # 从倒数第二个元素开始向左扫描
while i >= 0 and arr[i] >= arr[i + 1]:
    i -= 1

• 逻辑：从右向左寻找第一个满足arr[i] < arr[i+1]的位置i（即最后一个升序位置）。
• 示例（以arr = [1,3,2]为例）：
  • 初始i = 1（索引1对应元素3）。
  • 检查arr[1] = 3和arr[2] = 2：3 >= 2，不满足升序，i减1（i=0）。
  • 检查arr[0] = 1和arr[1] = 3：1 < 3，满足条件，停止。最终i=0。
• 意义：i是最后一个可以增大的位置（若i=-1，说明数组完全降序，是最后一个排列）。

3. 判断是否是最后一个排列

if i == -1:
    return None

• 当i=-1时，说明数组是完全降序（如[3,2,1]），没有更大的排列，返回None结束。

4. 寻找关键位置j（比arr[i]大的最小元素）

j = len(arr) - 1  # 从末尾开始向左扫描
while arr[j] <= arr[i]:
    j -= 1

• 逻辑：从右向左寻找第一个比arr[i]大的元素位置j。
• 示例（接前例，arr = [1,3,2]，i=0，arr[i]=1）：
  • 初始j=2（元素2）。
  • 检查arr[2] = 2 > 1，满足条件，停止。最终j=2。
• 意义：arr[j]是i右侧比arr[i]大的最小元素，交换后能保证排列尽可能小。

5. 交换arr[i]和arr[j]

arr[i], arr[j] = arr[j], arr[i]

• 示例（接前例）：交换后数组变为[2,3,1]。
• 意义：将arr[i]增大为下一个可能的最小值，确保排列比当前大。

6. 反转i+1到末尾的元素（得到最小后续排列）

arr[i + 1:] = arr[i + 1:][::-1]

• 逻辑：将i+1到末尾的子数组反转（变为升序）。
• 示例（接前例，i=0，i+1到末尾的子数组是[3,1]）：反转后变为[1,3]，最终数组为[2,1,3]。
• 意义：i右侧的元素原本是降序（因为i是最后一个升序位置），反转后变为升序，得到最小的后续排列，确保整体是下一个字典序排列。

7. 返回新排列

return arr

• 返回生成的下一个字典序排列。

二、主程序（输入处理与排列生成）

1. 输入n并校验

n = int(input())
if n < 1:
    pass  # 输入无效时不处理
else:
    # 生成初始排列并循环输出

• 读取用户输入的整数n，若n<1（如0或负数），不执行后续逻辑。

2. 生成初始排列

current = list(range(1, n + 1))  # 初始排列[1,2,…,n]

• 初始排列是最小的字典序排列（升序，如n=3时为[1,2,3]）。

3. 循环生成并输出所有排列

while True:
    # 格式化输出：每个数字占5场宽（右对齐）
    line = ''.join([f"{num:5d}" for num in current])
    print(line)
    current = next_permutation(current)  # 生成下一个排列
    if current is None:  # 无下一个排列时结束循环
        break

• 格式化输出：使用f"{num:5d}"将每个数字格式化为5字符宽度（右对齐，不足补空格）。例如，数字1会被格式化为 1（4个空格+1）。
• 循环逻辑：从初始排列开始，不断调用next_permutation生成下一个排列，直到返回None（表示已生成所有排列）。

三、完整执行流程示例（以n=3为例）

1. 初始排列：current = [1,2,3] → 输出 1 2 3。
2. 第一次调用next_permutation：
   • i从1开始，检查arr[1]=2和arr[2]=3：2 < 3，i=1。
   • j从2开始，arr[2]=3 > 2，交换arr[1]和arr[2] → [1,3,2]。
   • 反转i+1到末尾（无元素），返回[1,3,2] → 输出 1 3 2。
3. 第二次调用：生成[2,1,3] → 输出 2 1 3。
4. 第三次调用：生成[2,3,1] → 输出 2 3 1。
5. 第四次调用：生成[3,1,2] → 输出 3 1 2。
6. 第五次调用：生成[3,2,1] → 输出 3 2 1。
7. 第六次调用：i=-1，返回None → 循环结束。

最终输出6个排列（3! = 6），完全符合字典序。

四、总结

这段代码通过next_permutation函数迭代生成下一个字典序排列，避免了递归的栈开销，适合处理较大的n。核心逻辑是通过调整局部元素顺序（找升序位置i、交换i和j、反转后续元素），确保生成的排列是比当前大的最小排列。主程序则从初始排列开始，循环调用该函数并格式化输出，直到所有排列生成完毕。