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年才能完成整个列表。

所以，你可能要考虑如何生成只有你感兴趣的组合。