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

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

  •  
  •   longzhixin · 89 天前 · 809 次点击
    这是一个创建于 89 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目:

    有 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,那么这个数据量非常巨大,采用什么的方案写入文件并去重比较好呢?

    8 回复  |  直到 2019-09-10 20:31:28 +08:00
        1
    arrow8899   89 天前
    跟学生总数没关系吧,每个学生的选择都是独立互不影响的,50 个学生也就 A(50, 5) * 20 = 5085024000,去重可以用布隆过滤器。
        2
    wanganjun   89 天前
    用 byte 代替字符串:0-33 用一个 byte 表示足够了,一个数字组合占用空间 5 个 byte。

    这样一个数字组合就可以用一个 int64 来表示,去重功能就可以直接用比较 int64 是否相同就可以了
        3
    wanganjun   89 天前
    还可以再极端一点,0-33 用 4 个 bit 就可以表示,这样一个数字组合占用空间 2.5 个 byte,可以直接用 int32 表示
        4
    wanganjun   89 天前
    上一个回答好像不对。。。
        5
    layorlayor   89 天前
    1. 把 50 个人分成两堆,一边 25 人, 两边分别求出每个人数组合的状态,一共 2^25 种组合
    2. 从一边选 k 个人,0<=k<=20,那另一边选 20-k 个人,组合一下,复杂度 20 * (2^20)
    3. 以上口胡。
        6
    layorlayor   89 天前
    @layorlayor 好像说错了 忽略我吧
        7
    smdbh   89 天前 via iPhone
    如果大家选择一致就是 c33-5,有一个变化就是 c33-6,学生够多,就是 c33-33,然后全部加起来?
        8
    mathzhaoliang   89 天前
    你需要一个不重复不遗漏生成所有组合数的算法,而不是全部生成然后去重。
    可以参考 knuth 计算机程序设计艺术第四卷组合算法。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   904 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 24ms · UTC 19:01 · PVG 03:01 · LAX 11:01 · JFK 14:01
    ♥ Do have faith in what you're doing.