算法產生K個元件的子集在其總和

Question

的順序如果我有一個未排序的大組n整數（比如他們的2^20），並希望與每個（其中k很小，比如5）在k元件以產生子集增加他們的數量的順序，那麼最有效的方法是什麼？

爲什麼我需要以這種方式生成這些子集是我想找到滿足一定條件的最小和的k元素子集，因此我會將條件應用於每個k元素子集生成。

此外，該算法的複雜性是什麼？

也有同樣的問題在這裏：Algorithm to get every possible subset of a list, in order of their product, without building and sorting the entire list (i.e Generators)關於他們的產品生成訂單的子集，但它不適合我的需要，由於非常大的尺寸設定的n

我打算實現算法Mathematica，但也可以用C++或Python來完成。

Answer 1

如果你想要小的子集（稱之爲P）的屬性是相當普遍的，概率方法可以很好地工作：

1. 排序n整數（以百萬計的整數，即10秒到的MB的100S公羊，這應該不成問題），並且總和最小。請致電offset。
2. 生成一個隨機k -subset（例如，通過取樣k隨機數，模n）並檢查它是否爲P -ness。
3. 在匹配上，記下子集的總和。從中減去offset以找到任何k-等價總和的子集的最大元素的上限。
4. 將您的整數集合限制爲小於或等於此範圍的集合。
5. 重複（轉到2），直到在某些固定次數的迭代中找不到匹配項。

注意初始排序是O(n log n)。隱含在步驟4中的二進制搜索是O(log n)。

很明顯，如果P是如此罕見以至於隨機底池不太可能得到匹配，那麼這對你來說並不好。

Answer 2

你的意思是20個整數，或2^20？如果真的是2^20，那麼在找到滿足條件的一個之前，您可能需要經歷大量的(2^20 choose 5)子集。在一個現代的100k MIPS CPU上，假設只有一條指令可以計算一個集合並評估這個條件，那麼通過整個集合仍然需要3 quadrillion years。所以，如果你甚至需要經歷其中的一小部分，那麼在你的有生之年就不會完成。

即使整數的數量較小，這似乎是一個相當強大的方式來解決這個問題。我猜想你可能能夠在mixed integer program中將約束條件表達爲約束條件，在這種情況下，解決以下問題可能是比暴力枚舉更快速的獲得解決方案的方法。假設你的整數是w_i，i從1到N：

min sum(i) w_i*x_i 
    x_i binary 
    sum over x_i = k 
subject to (some constraints on w_i*x_i) 

如果事實證明你的MIP的linear programming relaxation很緊，那麼你會很幸運，並有解決問題的一個非常有效的方式，甚至對於2^20整數（例如：max-flow/min-cut problem）。另外，您可以使用column generation的方法來查找解決方案，因爲您可能有大量無法同時解決的值。

如果您更多地瞭解您感興趣的約束，我或其他人可能會爲您提出一個更具體的解決方案，它不涉及暴力枚舉。

Answer 3

即使千分之一的k大小的集合中只有1個滿足您的條件，仍然有太多的組合需要測試。我相信運行時會使用nCk（n選擇k）進行縮放，其中n是未排序列表的大小。 Andrew Mao的答案與此價值​​有關。 10^28/1000仍然是10^25。即使在每秒1000次測試中，這仍然是10秒22秒。 = 10^14年。

如果你被允許，我認爲你需要從你的大集合中消除重複的數字。刪除的每個副本都會大大減少您需要執行的評估數量。對列表進行排序，然後殺死它們。

另外，你在尋找單一的最佳答案嗎？誰將驗證答案，以及需要多長時間？我建議實施遺傳算法並在一夜之間運行一堆實例（只要你有時間）。這會產生一個非常好的答案，比宇宙的持續時間少得多。

Answer 4

下面是一個大致的方法來做你在說什麼。

首先，對列表進行排序。然後，考慮一些長度爲5的索引向量v，其對應於排序列表中的位置，其中最大索引是某個數字m，以及某個其他索引向量v'，其中某個最大索引m' > m。所有這些矢量v'的最小總和總是大於所有矢量v的最小和。

所以，這裏是你如何通過遍歷元素大約增加總和：

sort arr 

for i = 1 to N 
    for v = 5-element subsets of (1, ..., i) 
    set = arr{v} 
    if condition(set) is satisfied 
     break_loop = true 
     compute sum(set), keep set if it is the best so far 
    break if break_loop 

基本上，這意味着你不再需要檢查的(1, ..., n+1) 5元素的組合，如果你找到滿意的分配在(1, ..., n)，因爲任何滿意的任務與最大索引n+1將有一個更大的總和，你可以停止後設置。然而，沒有簡單的方法來循環使用(1, ..., n)的5種組合，同時保證總和總是增加，但至少當您在n處找到令人滿意的設置後，至少可以停止檢查。

Answer 5

這看起來是map-reduce的最佳人選（http://en.wikipedia.org/wiki/MapReduce）。如果您知道如何巧妙地對它們進行分區，以便在每個節點中均勻存在候選應用程序，那麼您可能會獲得很高的吞吐量。

完全的排序可能並不是真的需要，因爲地圖階段可以處理它。然後每個節點可以根據k元組驗證條件並將結果輸出到可以稍後聚合/減少的文件中。

如果您知道發生概率並且不需要所有結果，請嘗試查看概率算法以收斂到答案。