这是一个创建于 2233 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目：
有 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，那么这个数据量非常巨大，采用什么的方案写入文件并去重比较好呢？
 | 1 arrow8899 2019-09-10 17:16:20 +08:00  1 跟学生总数没关系吧，每个学生的选择都是独立互不影响的，50 个学生也就 A(50, 5) * 20 = 5085024000，去重可以用布隆过滤器。 |
 | 2 wanganjun 2019-09-10 18:26:05 +08:00 用 byte 代替字符串：0-33 用一个 byte 表示足够了，一个数字组合占用空间 5 个 byte。 这样一个数字组合就可以用一个 int64 来表示，去重功能就可以直接用比较 int64 是否相同就可以了 |
| 3 wanganjun 2019-09-10 18:28:55 +08:00 还可以再极端一点，0-33 用 4 个 bit 就可以表示，这样一个数字组合占用空间 2.5 个 byte，可以直接用 int32 表示 |
| 4 wanganjun 2019-09-10 18:30:41 +08:00 上一个回答好像不对。。。 |
 | 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. 以上口胡。 |
| 6 layorlayor 2019-09-10 19:32:38 +08:00 @layorlayor 好像说错了 忽略我吧 |
 | 7 smdbh 2019-09-10 20:19:45 +08:00 via iPhone 如果大家选择一致就是 c33-5，有一个变化就是 c33-6，学生够多，就是 c33-33，然后全部加起来？ |
 | 8 mathzhaoliang 2019-09-10 20:31:28 +08:00 1 你需要一个不重复不遗漏生成所有组合数的算法，而不是全部生成然后去重。 可以参考 knuth 计算机程序设计艺术第四卷组合算法。 |
 | 9 longzhixin OP @arrow8899 迟来的感谢，非常感谢 |
| 10 longzhixin OP @wanganjun 非常感谢 |
| 11 longzhixin OP @layorlayor 感谢 |
| 12 longzhixin OP @mathzhaoliang 专门买了本，看了组合算法 |
| 13 longzhixin OP @smdbh 感谢 |
Select Language