子集的有效计数

Question

我目前正在研究一个数学优化问题的算法，并且必须处理以下情况。

在很多情况下，算法都需要决定在这种情况下，哪一个子集S⊂N是最好的。

N={ 0，1，2，…，126,127 }

{ 0，1，2，3，4，5}(子集大小在0到5之间)

这使可能的子集总数为265.982.833。(binom(128，5) + binom(128，4) +…+ binom(128，0))

如果我预先计算所有可能的子集并将它们存储在一个数组中，那么这个数组将有265.982.833个条目，内存占用量约为1,27 GB，没有任何优化，也没有将子集作为字节数组进行简单存储。

在这种情况下，当算法需要知道特定子集中有索引的元素时，只需要查找表。然而，巨大的内存需求是不可接受的。

因此，我的问题基本上是，如果有人能够想出一种算法，有效地计算子集中的元素，基于索引i，而不需要预先计算数组。

编辑包括样本：

lookupTable = {}

lookupTable1 = {0}

..。

lookupTable127 = {126}

lookupTable128 = {127}

lookupTable129 = {0，1}

lookupTable130 = {0，2}

..。

lookupTable265982832 = {123,124,125,126,127}

Answer 1

简单的实现将使用位图(bitX == 1，意思是集合中存在项目X)，另一个约束是掩码中最多不能超过5位。它需要128位来表示一个集合。

使用素数乘积表示集合只需<64位/集(124.128‘位)(124:691,125:701,126:709,127:719,128:727}，它们的产品将适合64位，IICC。它仍然会浪费一些位(如OQ所示，一个好的枚举可以容纳32位)，但是通过GCD很容易检查两个集合的“重叠”公共项。

这两个方法都需要对值数组进行排序，并使用该数组中集合的秩作为其枚举值。