algorithm - 高效的子集枚举

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 的特定子集中时，只需要进行表查找。然而，巨大的内存需求是 Not Acceptable 。

所以我的问题基本上是，是否有人能想到一种算法来根据索引 i 有效地计算子集中的元素，而不是需要预先计算的数组。

---

编辑包含样本:
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)，并且存储成本不是很高(索引为 16 字节而不是 4 字节)。

如果您真的想为子集存储简明的索引，我会使用以下递归，其中 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) = Σ<sup>n</sup><sub>i=k</sub>S(i-1,k-1)
(用 jsMath 会看起来更好，grrr。)

这是另一种说法，我们将按最大元素的顺序生成集合，因此我们从集合 {0...k-1} 开始, 那么所有的集合都是 {k}作为最大的元素，然后是所有带有 {k+1} 的元素， 等等。在每组集合中，我们递归查找 (k-1) - 大小的集合，再次从最小的最大值开始，一直到比我们刚刚选择的最大值小 1。

因此我们可以计算出索引集中的最大值是S(n,k) 中的一个索引。通过连续减去 S(i-1, k-1)对于 i来自 k至 n直到结果是否定的；然后我们添加 {i}到结果集；减少 k 1 并用 n 重复现在设置为 i-1 .

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