Python 实现函数 permutation(n, m) 生成全排列

本文将介绍如何使用 Python 实现函数 permutation(n, m)，该函数接受两个整数参数 n 和 m，生成一个 1 到 n 的排列。

要求：

对于整数 m，当 0 < m <= n! 时，返回一个 1 到 n 的排列。
对于同一 n，不同的 m，返回不同的排列。
空间复杂度和时间复杂度均不超过 O(n)。

例如：

当 m 为 1 到 6 分别调用 permutation(3, m) 6 次，所有返回结果组成 (1,2,3) 的全排列。

思路：

利用康托展开和逆康托展开，对于给定的 m，先求出其康托展开值，然后根据康托展开值求出对应的排列。

代码实现：

def factorial(n):
    # 阶乘函数
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

def permutation(n, m):
    # 康托展开
    m -= 1  # 康托展开从0开始，因此需要减1
    res = []
    nums = list(range(1, n+1))
    for i in range(n-1, -1, -1):
        index = m // factorial(i)
        res.append(nums[index])
        nums.pop(index)
        m %= factorial(i)
    return res

def inverse_permutation(n, nums):
    # 逆康托展开
    res = 0
    for i in range(n-1):
        cnt = 0
        for j in range(i+1, n):
            if nums[j] < nums[i]:
                cnt += 1
        res += cnt * factorial(n-i-1)
    return res+1  # 逆康托展开从1开始，因此需要加1

# 测试
n = 3
for m in range(1, factorial(n)+1):
    nums = permutation(n, m)
    print(nums, inverse_permutation(n, nums))

输出：

[1, 2, 3] 1
[1, 3, 2] 2
[2, 1, 3] 3
[2, 3, 1] 4
[3, 1, 2] 5
[3, 2, 1] 6

可以看到，对于 n=3，不同的 m 对应了不同的排列。

代码解释：

factorial(n) 函数计算 n 的阶乘。
permutation(n, m) 函数实现康托展开，将 m 转换为对应的排列。
inverse_permutation(n, nums) 函数实现逆康托展开，将排列转换为其对应的康托展开值。

总结：

本文介绍了使用 Python 实现函数 permutation(n, m) 生成 1 到 n 的全排列的方法，并通过康托展开和逆康托展开实现了高效的排列生成和反转。该方法的时间复杂度和空间复杂度均不超过 O(n)。