n元素組合選擇r元素不重複（Objective-c）

Question

我有一個對象數組（n）。 我想通過一次選擇（r）元素來輸出一個唯一對象的數組。

例如： N = 600， R = 10

我們怎樣才能得到所有可能的獨特的解決方案的陣列？

我意識到這是二項式係數公式（也是解決方案集是巨大的），但我很難找出實現它的方法，不會超出內存限制。

某些可能有助於實現細節（從記憶關注點）的事情是，對於每種可能的組合，我都可以應用某些規則來確認它是否與我有任何相關性（在很多情況下，組合將無濟於事）。

Answer 1

這裏有一個簡單的算法，如果你調用足夠的次數，它可以讓你產生從0到n-1的所有整數的整數。該算法所做的是採用一個代表組合的r向量，並將其推到下一個組合（按字典順序排列）。您可以使用這樣的矢量來索引對象的矢量。

給定一個向量v0...vr-1：

• 找到最大的j < r這樣vj < n - r + j
• 增量元素j。
• 對於每個k這樣j < k和k < r，設置vk到vj + k - j

這裏有一個簡單，合理高效的C溶液（雖然不是每個人都會欣賞的風格）。如果當前組合是最後一個組合，則函數返回false。該向量應該初始化爲序列0...r-1，以遍歷整個可能性集合。

bool next_combination(int *comb, int n, int r) { 
    for (int j = r - 1, v = n - 1; j >= 0; --j, --v) { 
    if (comb[j] < v) { 
     for (v = comb[j] + 1; j < r; ++j, ++v) 
     comb[j] = v; 
     return true; 
    } 
    } 
    return false; 
} 

不過，我真的不認爲產生所有可能Ç值將是實際的，即使你不嘗試將它們全部存放在數組中。 C 是1,545,269,050,621,668,869,640。如果你可以在第二秒內（即每納秒一次）處理10 組合，它仍然需要約48,965年才能完成整個列表。

所以，你可能要考慮如何生成只有你感興趣的組合。