假设我有一组来自 [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!肯定不适合内存。有什么建议吗?
最佳答案
这是我的镜头:
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
想到在下一个数字增加之前有多少组合。但是,它仅适用于三个元素。我不能保证它是正确的。如果您将其与您的结果进行比较并提供一些反馈,那就太棒了。
关于c++ - 大集合的第 n 个或任意组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15058903/