V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
roker
V2EX  ›  程序员

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

  •  
  •   roker ·
    rokerdou · 2022-04-19 01:00:44 +08:00 · 899 次点击
    这是一个创建于 709 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目要求
    在数学中 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
        1
    roker  
    OP
       2022-04-19 01:17:00 +08:00
    补充 n<10,期望得到的算法时间复杂度 O(n)
    Ljxtt
        2
    Ljxtt  
       2022-04-19 02:26:20 +08:00 via Android   ❤️ 2
    逆康托展开?
    jony83
        3
    jony83  
       2022-04-19 09:26:11 +08:00
    自定义一个结构,存有 pass(经过的次数)和 end(以这个数为结尾的)
    jony83
        4
    jony83  
       2022-04-19 09:30:13 +08:00
    一个结构是一个线,数据的起点是不包含任何数字开头的。是 1 开头的建立以 1 开头的线。是 2 开头的建立 2 开头的线。end 用来判断是否重复了
    jony83
        5
    jony83  
       2022-04-19 09:35:40 +08:00
    每一个节点有 0 个 9 的分支线。你从头开始遍历每个节点就是了
    MoYi123
        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.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3925 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:27 · PVG 18:27 · LAX 03:27 · JFK 06:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.