用python实现函数permutationn m。要求：a 对于整数m当0m=n!返回一个1至n的排列b 对于同一n不同的m返回不同的排列c 空间复杂度和时间复杂度均不超过On例如：m为1至6分别调用permutation3 m6次所有返回结果组成123的全排列。

思路：利用康托展开和逆康托展开，对于给定的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对应了不同的排列