以分布式方式枚举组合

Question

我有一个问题,我必须分析500C5组合(255244687600)的东西.将其分布在10个节点的集群中,每个集群每秒处理大约10 ^ 6个组合,这意味着该作业将在大约7个小时内完成.

我遇到的问题是在10个节点上分配255244687600组合.我想给每个节点提供25524468760,但是我使用的算法只能顺序生成组合,我希望能够传递元素集和一系列组合指标,例如,[0 -10 ^ 7),[10 ^ 7,2.0 10 ^ 7)等,并让节点自己找出组合.

我目前使用的算法来自以下内容:

• http://howardhinnant.github.io/combinations.html

• Stack Overflow问题有效地计算矢量组合

我考虑过使用一个主节点,它枚举每个组合并将工作发送到每个节点.然而,从单个节点迭代组合并来回通信工作所产生的开销是巨大的,并且随后将导致主节点成为瓶颈.

是否有任何良好的组合迭代算法可以实现有效/最佳的分布式枚举？

Answer 1

您可能会在组合数字方面取得一些成功，它允许您使用简单的算法检索第N ( n /10) k组合；然后在十个节点中的每一个上运行next_combination算法n /10 次以进行迭代。

示例代码（C# 语言，但对于 C++ 程序员来说非常可读）可以在MSDN上找到。