c++ - 大集合的第 n 个或任意组合

Question

假设我有一组来自 [0, ....., 499] 的数字。目前正在使用 C++ std::next_permutation 顺序生成组合。作为引用，我拉出的每个元组的大小是 3，所以我返回顺序结果，例如 [0,1,2], [0,1,3], [0,1,4], ... [497,498,499]。

现在，我想并行化它所在的代码，因此这些组合的顺序生成将不再起作用。是否有任何现有的算法可以从 500 个数字中计算出 3 的 ith<​​ 组合？

我想确保每个线程，无论它获得的循环迭代如何，都可以根据它正在迭代的 i 计算一个独立的组合。因此，如果我想要线程 1 中 i=38 的组合，我可以在计算 [1,2,5] 的同时计算 i=0 在线程 2 中作为 [0,1,2].

编辑下面的陈述无关紧要，我自己搞混了

我查看了利用阶乘从左到右缩小每个单独元素的算法，但我不能将这些用作 500!肯定不适合内存。有什么建议吗？

Answer 1

这是我的镜头:

int k = 527; //The kth combination is calculated
int N=500; //Number of Elements you have
int a=0,b=1,c=2; //a,b,c are the numbers you get out

while(k >= (N-a-1)*(N-a-2)/2){
    k -= (N-a-1)*(N-a-2)/2;
    a++;
}
b= a+1;
while(k >= N-1-b){
    k -= N-1-b;
    b++;
}

c = b+1+k;


cout << "["<<a<<","<<b<<","<<c<<"]"<<endl; //The result

想到在下一个数字增加之前有多少组合。但是，它仅适用于三个元素。我不能保证它是正确的。如果您将其与您的结果进行比较并提供一些反馈，那就太棒了。