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

[longzhixin]

题目：

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

[arrow8899]

跟学生总数没关系吧，每个学生的选择都是独立互不影响的，50 个学生也就 A(50, 5) * 20 = 5085024000，去重可以用布隆过滤器。

[wanganjun]

用 byte 代替字符串：0-33 用一个 byte 表示足够了，一个数字组合占用空间 5 个 byte。

这样一个数字组合就可以用一个 int64 来表示，去重功能就可以直接用比较 int64 是否相同就可以了

[wanganjun]

还可以再极端一点，0-33 用 4 个 bit 就可以表示，这样一个数字组合占用空间 2.5 个 byte，可以直接用 int32 表示

[wanganjun]

上一个回答好像不对。。。

[layorlayor]

1. 把 50 个人分成两堆，一边 25 人， 两边分别求出每个人数组合的状态，一共 2^25 种组合
2. 从一边选 k 个人，0<=k<=20，那另一边选 20-k 个人，组合一下，复杂度 20 * (2^20)
3. 以上口胡。

[layorlayor]

@layorlayor 好像说错了 忽略我吧

[smdbh]

如果大家选择一致就是 c33-5，有一个变化就是 c33-6，学生够多，就是 c33-33，然后全部加起来？

[mathzhaoliang]

你需要一个不重复不遗漏生成所有组合数的算法，而不是全部生成然后去重。
可以参考 knuth 计算机程序设计艺术第四卷组合算法。

[longzhixin]

@arrow8899 迟来的感谢，非常感谢

[longzhixin]

@wanganjun 非常感谢

[longzhixin]

@layorlayor 感谢

[longzhixin]

@mathzhaoliang 专门买了本，看了组合算法

[longzhixin]

@smdbh 感谢