给定一个按顺序 (0-255) 排列的 256 个数字的列表，我想表达该列表中 128 个数字的子集。每个数字都是唯一的，不会重复。
表达这个子集的最紧凑的方式是什么？
到目前为止，我想出的是拥有一个 256 位长度的位数组并将适当的索引设置为 1。这种方法显然需要 256 位来表示 128 个值，但是否有不同的、更节省空间的方式？
谢谢!
最佳答案
有256个!/(128! * (256 - 128)!) 一组 256 个项目中的 128 个元素的独特组合，顺序无关紧要(参见 wiki 关于组合)。
如果您计算该数字并取以 2 为底的对数 - 您会发现它是 251.6。这意味着您至少需要 252 位来表示从 256 项中选择的 128 项的唯一选择。由于 .NET 无论如何都不能表示位(只能表示整个字节)- 没有理由真正找出如何做到这一点。
128 是这方面最差的数字。如果您选择 5 个元素或 256 个元素中的 251 个元素 - 可以用 34 位表示，尝试找到那种有效的表示形式会很有用。
关于c# - 用二进制表示子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43184710/