我目前正在研究数学优化问题的算法，必须处理以下情况。
在很多情况下，算法需要决定在这种情况下哪个子集 S ⊂ N 最好。
N = { 0， 1， 2， ...， 126， 127 }
|S|∈ { 0， 1， 2， 3， 4， 5 } (子集的大小介于 0 和 5 之间(
这给出了 265.982.833 的可能子集总数。(二进制(128， 5( + 二进制(128， 4( + ... + 二进制(128， 0((
如果我预先计算所有可能的子集并将它们存储在一个数组中，那么这个数组将有 265.982.833 个条目和大约 1,27 GB 的内存占用，而无需任何优化和幼稚地将子集存储为字节数组。
在这种情况下，当算法需要知道哪些元素位于索引为 i 的特定子集中时，只需要查找表。但是，巨大的内存要求是不可接受的。
所以我的问题基本上是，如果有人能想到一种算法来根据索引 i 有效地计算子集中的元素，而不是需要预先计算的数组。
编辑包含的示例：
查找表[0] = {}
查找表[1] = {0}
...
查找表[127] = {126}
查找表[128] = {127}
查找表[129] = {0， 1}
lookupTable[130] = {0， 2}
...
lookupTable[265982832] = {123， 124， 125， 126， 127}
从前面的子集构造每个子集很简单。将子集表示为 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会看起来更好。
这是另一种说法，我们将按最大元素的顺序生成集合，所以我们从集合{0...k-1}开始，然后是所有以{k}为最大元素的集合，然后是所有带有{k+1}的集合，依此类推。在每组集合中，我们递归以找到(k-1)大小的集合，同样从最小最大值开始，一直到比我们刚刚选择的最大值小一个。
因此，我们可以通过将i的S(i-1, k-1)从 k 减去 到 n 直到结果为负数，从而计算出索引集中索引的最大值S(n,k);然后我们将{i}添加到结果集中;将k减少 1 并重复n现在设置为 i-1 。
如果我们预先计算相关的S(n,k)表，其中大约有 640 个有效组合，我们可以使用二叉搜索而不是迭代来查找每一步的i，因此计算需要时间k log(n)，这并不可怕。
朴素实现将使用位图(bitX == 1 表示集合中存在项目 X( 另一个约束是掩码中不超过 5 位可以是一个。它需要 128 位来表示一个集合。
使用素数的乘积来表示集合，每组只需要 <64 位(第 124...128 个素数是 {124：691、125：701、126：709、127：719、128：727}，它们的乘积将适合 64 位 IICC。它仍然会浪费一些位(如OQ所示，一个好的枚举适合32位(，但是通过GCD很容易检查两组的"重叠"公共项目。
这两种方法都需要对值数组进行排序，并使用此数组中集合的秩作为其枚举值。