有效枚举子集

Question

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

在很多情况下，算法需要决定在这种情况下哪个子集S⊂N最好。 N = {0,1,2，...，126,127}
| S | ∈{0,1,2,3,4,5}（子集的大小在0和5之间）

这给出了可能的子集总数265.982.833。 （binom（128,5）+ binom（128,4）+ ... + binom（128,0））

如果我预先计算所有可能的子集并将它们存储在一个数组中，那么这个数组将有265.982。 833个条目和大约1.27GB的存储器占用空间，没有任何优化和子集作为字节数组的天真存储。

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

所以我的问题是，如果任何人都可以想到一个算法来有效地计算基于索引i的子集中的元素，而不是需要预先计算的数组。

---

EDIT包括样品：
LookupTable中[0] = {}
LookupTable中[1] = {0}
...
LookupTable中[127] = {126}
LookupTable中[128 ] = {127}
LookupTable中[129] = {0，1}
LookupTable中[130] = {0,2}
...
LookupTable中[265982832] = {123，124，125，126， 127}

Answer 1

从前面的子集构造每个子集很简单。将一个子集表示为一个128位数字也很简单（尽管显然大多数值不会映射到合格的子集上，而且我不知道问题中128的值是真实还是仅仅是一个示例。）这就是当然，我会用第一种方法;如果有效，则全部为O（1），存储成本不是极端的（对于索引而不是4个，则为16个字节）。

如果你真的想存储简洁指数的子集，我会使用大小≤ k的以下递归，其中S（N，K）代表所有的子集（或子集的计数）从数值< N：

s(n,0) = { {} }
s(n,k) = (s(n-1,k-1) ⊙ {n}) ⋃ s(n-1,k) if n ≥ k > 0
s(n,k) = {} if n < k

在操作者P ⊙ S意思是 “添加到S的P每个元素”（并因此结果是完全大小相同）。因此，被视为一个计数算法，我们得到：

S(n,0) = 1
S(n,k) = S(n-1,k-1) + S(n-1,k) if n ≥ k > 0
S(n,k) = 0 if n < k

第二递归可以重新表述为：

S(n,k) = Σni=kS(i-1,k-1)
（这会出来找更好地与jsMath，grrr。）

这是另一种说法，我们将按顺序生成集最大的元素，所以我们从集合{0...k-1}开始，然后所有的集合以{k}为最大元素，然后用{k+1}等全部集合，依此类推。在每组集合中，我们递归找到(k-1)大小的集合，再次以最小最大值开始，并且以小于我们刚刚选择的最大值的方式工作。

因此，我们可以找出依次减去S(i-1, k-1)为i从k到n直到结果是阴性为S(n,k)指数索引集中的最大值;然后我们将{i}添加到结果集中;将k减1并重复n现在设置为i-1。

如果我们预先计算的S(n,k)相关表格，其中有大约640有效组合，我们可以使用二进制搜索，而不是迭代找到i在每一步，所以计算需要时间k log(n)，这是不可怕的。

Answer 2

幼稚的实现将使用位图（bitX == 1表示项X存在于集合中）另外的约束是掩码中不超过5位可以是一个。它需要128位来表示一个集合。

使用primenumbers来表示集合只需要<每组64位（124 ... 128'的主数字是{124：691,125：701,126：709,127：719,128 ：727}，它们的产品将适合64位IICC，它仍然会浪费一些位（如OQ所示，一个很好的枚举将适合32位），但是很容易检查“重叠”两套通过他们的GCD的手段。

这两种方法都需要值的数组进行排序，并使用该数组作为枚举值内一组的秩。