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

求助:排列组合问题: 将所有组合写入文件方案求助

  •  
  •   longzhixin · 2019-09-10 15:11:48 +08:00 · 1760 次点击
    这是一个创建于 1903 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目:

    有 34 个学生,每个学生从 0-33 个数字中选择了 5 个数字,作为输入;

    如下图:

    `

    06,10,14,16,26
    14,20,21,22,26
    01,10,11,12,13
    11,01,12,02,17
    10,11,12,17,19
    09,17,13,15,32
    12,19,20,21,22
    06,13,29,30,17
    20,30,33,06,08
    04,08,14,20,30
    12,15,17,20,29
    04,11,15,21,26
    01,06,12,20,29
    01,02,06,11,23
    02,27,20,12,10
    02,10,17,25,26
    08,18,19,20,28
    10,21,25,28,29
    02,08,18,27,32
    05,20,21,27,33
    07,12,18,27,32
    13,15,18,20,22
    01,03,04,07,09
    05,06,12,21,30
    07,12,18,27,32
    02,03,06,08,15
    02,03,06,10,16
    14,15,19,25,06
    25,26,27,28,29
    04,01,14,25,30
    01,02,30,31,32
    04,05,14,15,29
    03,15,23,32,33
    01,05,26,12,33
    

    `

    现在随机从 34 个学生中挑选 5 名学生,合并他们选择的所有数字组合;将这些数字组合全部写入文件,要求要去重重复的组合。

    情形一: 如果不去重,那么组合数就有:$C^{5}_{34}$组合数,总共为 278256, 写入文件中数据量不大;

    但是目前遇到的问题:

    如果学生数为 50 个,求 20 个学生选择的所有组合,那么所有的组合$C^{20}_{50}$组合数为:47129212243960,那么这个数据量非常巨大,采用什么的方案写入文件并去重比较好呢?

    13 条回复    2020-01-03 23:35:44 +08:00
    arrow8899
        1
    arrow8899  
       2019-09-10 17:16:20 +08:00   ❤️ 1
    跟学生总数没关系吧,每个学生的选择都是独立互不影响的,50 个学生也就 A(50, 5) * 20 = 5085024000,去重可以用布隆过滤器。
    wanganjun
        2
    wanganjun  
       2019-09-10 18:26:05 +08:00
    用 byte 代替字符串:0-33 用一个 byte 表示足够了,一个数字组合占用空间 5 个 byte。

    这样一个数字组合就可以用一个 int64 来表示,去重功能就可以直接用比较 int64 是否相同就可以了
    wanganjun
        3
    wanganjun  
       2019-09-10 18:28:55 +08:00
    还可以再极端一点,0-33 用 4 个 bit 就可以表示,这样一个数字组合占用空间 2.5 个 byte,可以直接用 int32 表示
    wanganjun
        4
    wanganjun  
       2019-09-10 18:30:41 +08:00
    上一个回答好像不对。。。
    layorlayor
        5
    layorlayor  
       2019-09-10 19:23:02 +08:00
    1. 把 50 个人分成两堆,一边 25 人, 两边分别求出每个人数组合的状态,一共 2^25 种组合
    2. 从一边选 k 个人,0<=k<=20,那另一边选 20-k 个人,组合一下,复杂度 20 * (2^20)
    3. 以上口胡。
    layorlayor
        6
    layorlayor  
       2019-09-10 19:32:38 +08:00
    @layorlayor 好像说错了 忽略我吧
    smdbh
        7
    smdbh  
       2019-09-10 20:19:45 +08:00 via iPhone
    如果大家选择一致就是 c33-5,有一个变化就是 c33-6,学生够多,就是 c33-33,然后全部加起来?
    mathzhaoliang
        8
    mathzhaoliang  
       2019-09-10 20:31:28 +08:00   ❤️ 1
    你需要一个不重复不遗漏生成所有组合数的算法,而不是全部生成然后去重。
    可以参考 knuth 计算机程序设计艺术第四卷组合算法。
    longzhixin
        9
    longzhixin  
    OP
       2020-01-03 23:34:21 +08:00
    @arrow8899 迟来的感谢,非常感谢
    longzhixin
        10
    longzhixin  
    OP
       2020-01-03 23:34:31 +08:00
    @wanganjun 非常感谢
    longzhixin
        11
    longzhixin  
    OP
       2020-01-03 23:34:54 +08:00
    @layorlayor 感谢
    longzhixin
        12
    longzhixin  
    OP
       2020-01-03 23:35:12 +08:00
    @mathzhaoliang 专门买了本,看了组合算法
    longzhixin
        13
    longzhixin  
    OP
       2020-01-03 23:35:44 +08:00
    @smdbh 感谢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4921 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 10:00 · PVG 18:00 · LAX 02:00 · JFK 05:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.