大集合的第n个或任意组合

Question

说我有一组数字[0, ....., 499].目前正在使用C++顺序生成组合std::next_permutation.作为参考,我提取的每个元组的大小是3,所以我返回顺序结果,如[0,1,2], [0,1,3], [0,1,4], ... [497,498,499].

现在,我想并行化这个代码所在的代码,因此这些组合的顺序生成将不再起作用.是否存在用于计算ith500个数字中的3个组合的现有算法？

我想确保每个线程,无论它获得的循环迭代如何,都可以根据迭代的内容计算一个独立的组合i.因此,如果我想要i=38在线程1中进行组合,我可以计算[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

考虑到下一个数字增加之前有多少组合.但它只适用于三个元素.我无法保证这是正确的.如果你将它与你的结果进行比较并提供一些反馈,那将会很酷.