有效枚举子集

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,27 GB的内存占用,而没有任何优化和子集作为字节数组的幼稚存储.

在这种情况下,当算法需要知道哪些元素在索引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字节).

如果你真的想存储子集的简明索引,我会使用下面的递归,其中S(n,k)表示大小≤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"(因此结果与完全相同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)-sized集合,再次从最小值开始,并以比我们刚刚选择的最大值小一个的方式工作.

因此,我们可以找出在索引集的索引中的最大值S(n,k)依次减去S(i-1, k-1)了i从k到n直至其结果将是负的; 然后我们添加{i}到结果集; 减少k1并重复,n现在设置为i-1.

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