有效枚舉子集

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.27GB的存儲器佔用空間，沒有任何優化和子集作爲字節數組的天真存儲。

在這種情況下，當算法需要知道具有索引i的特定子集中的哪些元素時，只需要查找表。但是巨大的內存需求是不可接受的。

所以我的問題是，如果任何人都可以想到一個算法來有效地計算基於索引i的子集中的元素，而不是需要預先計算的數組。

---

EDIT包括樣品：
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），存儲成本不是極端的（對於索引而不是4個，則爲16個字節）。

如果你真的想存儲簡潔指數的子集，我會使用大小≤ k的以下遞歸，其中S（N，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每個元素」（並因此結果是完全大小相同）。因此，被視爲一個計數算法，我們得到：

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)大小的集合，再次以最小最大值開始，並且以小於我們剛剛選擇的最大值的方式工作。

因此，我們可以找出依次減去S(i-1, k-1)爲i從k到n直到結果是陰性爲S(n,k)指數索引集中的最大值;然後我們將{i}添加到結果集中;將k減1並重復n現在設置爲i-1。

如果我們預先計算的S(n,k)相關表格，其中有大約640有效組合，我們可以使用二進制搜索，而不是迭代找到i在每一步，所以計算需要時間k log(n)，這是不可怕的。

Answer 2

幼稚的實現將使用位圖（bitX == 1表示項X存在於集合中）另外的約束是掩碼中不超過5位可以是一個。它需要128位來表示一個集合。

使用primenumbers來表示集合只需要<每組64位（124 ... 128'的主數字是{124：691,125：701,126：709,127：719,128 ：727}，它們的產品將適合64位IICC，它仍然會浪費一些位（如OQ所示，一個很好的枚舉將適合32位），但是很容易檢查「重疊」兩套通過他們的GCD的手段。

這兩種方法都需要值的數組進行排序，並使用該數組作爲枚舉值內一組的秩。