用任意语言实现函数permutation(n, m)。要求： a. 对于整数m，当0<m<=n!，返回一个1至n的排列 b. 对于同一n，不同的m，返回不同的排列 c. 空间复杂度和时间复杂度均不超过O(n) 例如：m为1至6分别调用permutation(3, m)6次，所有返回结果组成(1,2,3)的全排列。

以下是Python代码实现：

def permutation(n, m):
    if m <= 0 or m > factorial(n):
        return []
    
    res = []
    nums = list(range(1, n+1))
    m -= 1  # 将m转化为下标，方便计算
    for i in range(n-1, -1, -1):
        idx, m = divmod(m, factorial(i))
        res.append(nums[idx])
        del nums[idx]
    
    return res

思路：

- 将1至n的数保存到一个列表nums中。
- 将m减1，将m转化为0至(n-1)!-1之间的数，方便计算。
- 从大到小枚举1至n的数，对于第i位，先计算它可以取哪些数，再根据m确定它所在的下标idx。
- 将nums[idx]添加到结果列表res中，并从nums中删除该数。
- 重复步骤3和步骤4，直到计算完所有位。

时间复杂度为O(n)，空间复杂度为O(n)。注意，需要提前定义阶乘函数factorial(n)。

相关问题

用任意语言实现函数permutation(n, m)。要求： a. 对于整数m，当0<m<=n!，返回一个1至n的排列 b. 对于同一n，不同的m，返回不同的排列 c. 空间复杂度和时间复杂度均不超过O(n)

以下是 Python 代码实现，使用了康托展开和康托展开的逆运算：

def permutation(n, m):
    # 阶乘
    fact = 1
    for i in range(2, n+1):
        fact *= i

    if m <= 0 or m > fact:
        return None

    # 康托展开
    m -= 1  # 将 m 转化为从 0 开始的下标
    nums = list(range(1, n+1))
    res = []
    for i in range(n-1, -1, -1):
        fact //= (i+1)
        index = m // fact
        m %= fact
        res.append(nums[index])
        nums.pop(index)

    return res

使用时，调用`permutation(n, m)`即可获取一个 1 到 n 的排列，其中 m 表示不同的排列。

解释一下函数的实现：

1. 首先计算 n 的阶乘，用于判断 m 是否在合法范围内。
2. 将 m 转化为从 0 开始的下标，方便后续计算。
3. 对于每个数字，计算它在当前剩余数字中的下标，使用康托展开公式计算出它的实际值，并将其从剩余数字中删除。重复该过程即可得到所有数字。

该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。

用任意语言实现函数permutation(n, m)。要求: a. 对于整数m,当0<m<=n!,返回一个1至n的排列 b. 对于同一n,不同的m,返回不同的排列 c. 空间复杂度和时间复杂度均不超过O(n)

以下是 Python 语言实现的函数 `permutation(n, m)`：

def permutation(n, m):
    nums = list(range(1, n+1))
    res = []
    factorial = 1
    for i in range(1, n+1):
        factorial *= i
    m -= 1
    while n > 0:
        factorial //= n
        index = m // factorial
        res.append(nums.pop(index))
        m %= factorial
        n -= 1
    return res

该函数的实现思路是利用阶乘的性质，将 m 转换为 n 个数字的排列中第几个排列，然后通过不断地计算余数和商来得到每个位置对应的数字。

具体地，我们设要求的排列为 $p_1, p_2, ..., p_n$，则第 $i$ 个位置可以选择的数字为 $1,2,...,n$ 中没有被选过的数字中第 $i$ 大的数字，设第 $i$ 个位置选的数字为 $x_i$，则可以得到如下的式子：

$$m = (x_1 - 1) \times (n-1)! + (x_2 - 1) \times (n-2)! + ... + (x_n - 1) \times 0!$$

上述式子中每一项都是该位置选择的数字对总方案数的贡献，因为前面的位置已经选定了对应的数字，所以剩下的数字中第 $i$ 大的数字的排名为 $x_i$。

我们可以通过不断地计算 $m$ 对 $(n-1)!$ 的商和余数来得到每个位置选的数字。具体地，我们从 $n$ 到 $1$ 遍历每个位置，每次计算出当前位置选的数字在剩下的数字中的排名，然后将该数字从剩下的数字中删除。最后返回得到的排列即可。

该算法的时间复杂度为 $O(n)$，空间复杂度也为 $O(n)$。