4

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

在很多情况下，算法需要决定在这种情况下哪个子集 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 有效地计算子集中的元素，而不是需要预先计算的数组。

编辑包括示例：
lookupTable[0] = {}
lookupTable[1] = {0}
...
lookupTable[127] = {126}
lookupTable[128] = {127}
lookupTable[129] = {0, 1}
lookupTable[ 130] = {0, 2}
...
查找表[265982832] = {123, 124, 125, 126, 127}

4

2 回答 2

5

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

如果您真的想为子集存储简明索引，我将使用以下递归，其中 S(n,k) 表示值 < n 中大小≤ k 的所有子集（或子集的计数）：

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。）

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

S(n,k)因此，我们可以通过连续减去S(i-1, k-1)for ifrom kton直到结果为负数，找出索引集合中索引 in 的最大值是多少；然后我们添加{i}到结果集中；减少k1 并重复n现在设置为i-1.

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

于 2013-03-27T03:13:34.977 回答
0

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

使用素数的乘积来表示集合只需要 <64 位/集合（第 124...128 个素数是 {124:691, 125:701, 126:709, 127:719, 128:727}，并且他们的产品将适合 64 位，IICC。它仍然会浪费一些位（一个好的枚举将适合 32 位，如 OQ 所示），但很容易通过以下方式检查两组的“重叠”公共项他们的 GCD。

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

于 2013-03-27T19:57:36.200 回答