高效枚举子集

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}
...
lookupTable[265982832] = {123, 124, 125, 126, 127}


我认为如果不知道选择S的基数和成员所使用的标准,回答这个问题可能会很困难。N的元素是否可以根据它们的索引计算? - angelatlarge
你只是想要一个快速且内存高效的循环(或迭代器)来遍历集合,还是你实际上需要编写高效的代码(为什么?)? - Andrej Bauer
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) = Σn(i=k)S(i-1,k-1)
(这将通过jsMath显示得更好,呃。)
这是另一种说法,即我们将按最大元素的顺序生成集合,因此我们从集合{0...k-1}开始,然后是所有具有{k}作为最大元素的集合,然后是所有具有{k+1}的集合等等。在每组集合中,我们递归以找到(k-1)大小的集合,同样从最小的最大值开始,并向上工作到刚刚选择的最大值减少1。
因此,我们可以通过反复从S(i-1,k-1)到n减去i来确定索引集中的最大值,直到结果为负数;然后我们将{i}添加到结果集中;将k减1并重复,现在将n设置为i-1。
如果我们预先计算S(n,k)的相关表格(大约有640个有效组合),我们可以使用二分搜索而不是迭代来找到每个步骤中的i,因此计算时间为k log(n),这并不糟糕。

非常感谢。我没有想到你的第一种方法使用128位数字。看起来这比任何枚举方法都要好得多。 - raisyn
1
@Knoothe:维基百科的解释比我的更优雅。而且他们可以使用真正的数学公式。 - rici

0

天真的实现将使用位图(bitX == 1表示集合中存在项目X)。另一个限制是掩码中不能有超过5个位为1。需要128位来表示一个集合。

使用质数乘积来表示集合只需要<64位每个集合(第124...128个质数是{124:691,125:701,126:709,127:719,128:727},它们的乘积将适合于64位,IICC。仍然会浪费一些位(好的枚举将适合于32位,如OQ所示),但可以通过它们的GCD检查两个集合的“重叠”公共项。

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


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接