algorithm - 子集的高效枚举

我目前正在研究数学优化问题的算法，并且必须处理以下情况。在很多情况下，算法需要决定在这种情况下哪个子集 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 有效地计算子集中的元素，而不是需要预先计算的数组。编辑包括 sample :查找表[0] = {}查找表[1] = {0}...查找表[127] = {126}查找表[128] = {127}查找表[129] = {0, 1}查找表[130] = {0, 2}...查找表[265982832] = {123, 124, 125, 126, 127} 最佳答案 从前面的子集构造每个子集很简单。将子集表示为 128 位数字也很简单(尽管显然大多数值不会映射到合格的子集上，而且我不知道问题中的 128 值是真实的还是只是一个示例。)就是这样当然是我会使用的第一种方法；如果它有效，则全部为 O(1) 并且存储成本并不极端(索引为 16 字节而不是 4 字节)。如果你真的想为子集存储简洁的索引，我会使用下面的递归，其中 S(n,k) 代表所有大小 ≤ k 的子集(或子集的计数)从值 s(n,0) = { {} }s(n,k) = (s(n-1,k-1) ⊙ {n}) ⋃ s(n-1,k) if n ≥ k > 0s(n,k) = {} if n < k其中运算符 P ⊙ S 表示“将 S 添加到 P 的每个元素”(因此结果与 P 的大小完全相同)。因此，将其视为计数算法，我们得到:S(n,0) = 1S(n,k) = S(n-1,k-1) + S(n-1,k) if n ≥ k > 0S(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(n,k)到S(i-1, k-1)依次减去i for k的n，直到结果为负，来计算{i}中某个索引在indexed set中的最大值是多少；然后我们将 k 添加到结果集中；将 n 减少 1 并重复 i-1 现在设置为 S(n,k) 。如果我们预先计算 i 的相关表，其中大约有 640 个有效组合，我们可以使用二进制搜索而不是迭代来找到每一步的 k log(n) ，因此计算需要时间 ojit_code ，这并不可怕。关于algorithm - 子集的高效枚举，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15649331/