一道全序列排序的算法题求算法

[roker]

题目要求
在数学中 n 个元素的排序序列有 n ！种，我们将 1 到 n 的连续自然数进行全序列排序，会有 n ！个排序，排序形成的结果数据按从小到大排列。
编写一个程序
实现输入 x 和 n ，输出 n!种排序中第 x 小的自然数排序序列。


举例 n=2; 全序列排序有 2 个种，1 ，2 和 2 ，1
程序
输入 x=1 ，则输出 1 ，2
输入 x=2 ，则输出 2 ，1

算法要求
不允许暴力递归，进行计算，因为最坏的复杂度是 o(n!)，性能太差
不允许存储全序列 n ！个数组，全序列数组针对 n 较大的情况下，空间占用过大。
尽可能降低算法时间复杂度。

看看哪个大神会做，我在编写加密算法遇到的一个问题

[roker]

补充 n<10,期望得到的算法时间复杂度 O(n)

[Ljxtt]

逆康托展开？

[jony83]

自定义一个结构，存有 pass(经过的次数)和 end(以这个数为结尾的)

[jony83]

一个结构是一个线，数据的起点是不包含任何数字开头的。是 1 开头的建立以 1 开头的线。是 2 开头的建立 2 开头的线。end 用来判断是否重复了

[jony83]

每一个节点有 0 个 9 的分支线。你从头开始遍历每个节点就是了

[MoYi123]

def sv(n, rank):
____ans = []
____tmp = math.factorial(len(n))
____for i in range(len(n)):
________tmp //= len(n)
________ans.append(n.pop(rank // tmp))
________rank %= tmp
____return ans
sv([0, 1, 2, 3, 4], 11)


就这样写吧, 需要注意一下 int 溢出的问题.
n 很大的话数据结构换成 pb_ds.