如何生成1到n的所有n!种排列列表？实现相关函数方案

一、生成所有排列的函数 #

方法1：递归回溯法 #

核心逻辑是每次固定一个位置的元素，递归生成剩余元素的排列，再将固定元素与剩余排列组合起来。以Python为例：

def generate_all_permutations(n):
    nums = list(range(1, n+1))
    result = []
    
    def backtrack(current, remaining):
        if not remaining:
            result.append(current.copy())
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
    
    backtrack([], nums)
    return result

# 测试n=3的情况
for p in generate_all_permutations(3):
    print(p)

运行后会输出你给出的6种排列结果。

方法2：利用内置库（Python） #

Python的itertools.permutations可以直接生成全排列，代码更简洁：

import itertools

def generate_all_permutations(n):
    nums = list(range(1, n+1))
    return [list(p) for p in itertools.permutations(nums)]

# 测试
for p in generate_all_permutations(3):
    print(p)

二、每次返回下一个排列的函数 #

这里用经典的「下一个排列」算法，步骤如下：

1. 从数组末尾往前找，找到第一个满足nums[i] < nums[i+1]的索引i（如果找不到，说明当前是最后一个排列，返回第一个排列）；
2. 再从末尾往前找，找到第一个大于nums[i]的元素索引j；
3. 交换nums[i]和nums[j]；
4. 反转i+1到数组末尾的元素，得到下一个排列。

Python实现代码：

def next_permutation(nums):
    # 找第一个升序位置i
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1
    # 如果找到i
    if i >= 0:
        # 找第一个比nums[i]大的j
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        # 交换i和j
        nums[i], nums[j] = nums[j], nums[i]
    # 反转i+1到末尾
    nums[i+1:] = nums[i+1:][::-1]
    return nums.copy()

# 测试用法：从初始排列开始，循环获取下一个排列
n = 3
current = list(range(1, n+1))
seen = set()
seen.add(tuple(current))
print(current)
while True:
    current = next_permutation(current)
    if tuple(current) in seen:
        break  # 回到初始排列，停止循环
    seen.add(tuple(current))
    print(current)

运行这段代码会依次输出所有排列，和你给出的顺序一致。

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