请不要在回答技术问题时复制粘贴 AI 生成的内容 style type="text/css"> #Wrapper { background-color: #e2e2e2; background-image: url("/static/img/shadow_light.png"), url("//cdn.v2ex.com/assets/bgs/circuit.png"); background-repeat: repeat-x, repeat-x; } #Wrapper.Night { background-color: #1f2e3d; background-image: url("/static/img/shadow.png"), url("//cdn.v2ex.com/assets/bgs/circuit_night.png"); background-repeat: repeat-x, repeat-x; background-size: 20px 20px, 162.5px 162.5px; }
这是一个创建于 1300 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目要求
在数学中 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