在二进制中表示子集

Question

给定一个按顺序排列的256个数字列表（0-255），我想表达这个列表中的128个数字子集。每个数字都将是唯一的，不重复。

如何以最紧凑的方式表达这个子集？

到目前为止，我想到的方法是使用一个长度为256的位数组，并将适当的索引设置为1。这种方法显然需要256位来表示128个值，但是否有不同的、更节省空间的方法呢？

谢谢！

- Kozzy

---

所选数字之间是否存在关联？ - xtofl

@xtofl - 不，除了128个数字是256个数字列表中的元素之外，它们之间没有任何关系。 - Kozzy

你是想要表示任意子集，还是有一种方法可以确定索引？ - Abion47

256位是32字节，这还不错。 - jdweng

@Abion47 - 不，子集的顺序并不重要，也与较大的集合无关。 - Kozzy

Answer 1

在一个包含256个项目的集合中，从中选择128个元素且顺序不重要，有256! / (128! * (256 - 128)!)种独特的组合（关于组合请参见wiki）。

如果你计算这个数字并取以2为底的对数，你会发现它是251.6。这意味着你需要至少252位来表示从256个项目中选择128个项目的唯一选择。由于.NET无法表示位（只能表示整个字节），因此没有必要实际找出如何完成这个任务。

128是在这方面最糟糕的数字。如果你选择5个元素或者从256个项目中选择251个元素，那么可以用34位表示，并且尝试找到这种有效的表示方式是有用的。

- Evk

---

如果子集包含来自256个数字列表的64个元素，那么是否可以使用更压缩的表示方式？也许是64位或更少？ - Kozzy

对于64位，仍然是204位（即26个完整的字节），理论上可以节省6个字节。 - Evk

Answer 2

由于您不关心子集的顺序，也不关心将每个元素恢复到原始数组中的位置，因此这只是产生数组的随机子集的情况，类似于从牌堆中抽取卡牌。

要从数组中获取唯一元素，您可以简单地对源数组进行洗牌，然后在前X个索引处取出若干元素：

int[] srcArray = Enumerable.Range(0, 256).ToArray();

Random r = new Random();
var subset = srcArray.OrderBy(i => r.Next()).Take(128).ToArray();

注意：我使用上述随机化方法是为了保持示例简洁。对于更强大的洗牌方法，我建议使用Fisher-Yates算法，如this post所述。

- Abion47

---

我正在尝试用少于256位来表示子集。这将创建一个无法以这种方式表达的数组！非常感谢您的努力。 - Kozzy

@Kozzy 嗯，你想做的事情是无法完成的，所以这是一种能够产生类似效果的方法。我能想到的唯一办法就是洗牌源数组，然后任意定义子集为数组的前X个元素，但那不会是子集的独立表示，所以我不认为那算数。 - Abion47

我担心那就是答案。试一试看是否我错过了什么简单的东西也是值得的。非常感谢你的时间和帮助！ - Kozzy