这是一个创建于 985 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目要求
在数学中 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 较大的情况下，空间占用过大。
尽可能降低算法时间复杂度。
看看哪个大神会做，我在编写加密算法遇到的一个问题
在数学中 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 较大的情况下，空间占用过大。
尽可能降低算法时间复杂度。
看看哪个大神会做，我在编写加密算法遇到的一个问题
 |
1
roker OP 补充 n<10,期望得到的算法时间复杂度 O(n)
|
 |
2
Ljxtt 2022-04-19 02:26:20 +08:00 via Android  2
逆康托展开？
|
 |
3
jony83 2022-04-19 09:26:11 +08:00
自定义一个结构，存有 pass(经过的次数)和 end(以这个数为结尾的)
|
|
4
jony83 2022-04-19 09:30:13 +08:00
一个结构是一个线，数据的起点是不包含任何数字开头的。是 1 开头的建立以 1 开头的线。是 2 开头的建立 2 开头的线。end 用来判断是否重复了
|
|
5
jony83 2022-04-19 09:35:40 +08:00
每一个节点有 0 个 9 的分支线。你从头开始遍历每个节点就是了
|
 |
6
MoYi123 2022-04-19 14:31:56 +08:00
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. |
Select Language