Take the 2-minute tour ×

I have a problem where I must analyse 500C5 combinations (255244687600) of something. Distributing it over a 10 node cluster where each cluster processes roughly 10^6 combinations per second means the job will be complete in about 7hours.

The problem I have is distributing the 255244687600 combinations over the 10 nodes. I'd like to present each node with 25524468760, however the algorithms I'm using can only produce the combinations sequentially, I'd like to be able to pass the set of elements and a range of combination indicies eg: [0-10^7) or [10^7,2.0 10^7) etc and have the nodes themselves figure out the combinations.

The algorithms I'm using at the moment are from the following:


A logical question

I've considered using a master node, that enumerates each of the combinations and sends work to each of the nodes, however the overhead incurred in iterating the combinations from a single node and communicating back and forth work is enormous, and will subsequently lead to the master node becoming the bottleneck.

Are there any good combination iterating algorithms geared up for efficient/optimal distributed enumeration?

share|improve this question
Not much experience in this area, but it sounds like a problem that google MapReduce could be applied to. –  Merlyn Morgan-Graham Jan 15 '11 at 8:27
MapReduce is irrelevant here, as the question is about the "Map" part of the term: How does one efficiently map a n-choose-k space problem into m parts without the need for a central distributor. –  Matthieu N. Jan 15 '11 at 8:30
@Reyzooti: Hence the "not much experience". Happy to be corrected, though. –  Merlyn Morgan-Graham Jan 15 '11 at 8:34
Permutations can be systematically numbered using the factorial number system. In your case only one out of each 495!*5! permutation is a relevant combination. So I gather, you can probably compute the start permutation = combination for each node, then just go on from there. This idea may pan out or not. Depending on the details; it's just an idea. ;-) Cheers & hth., –  Cheers and hth. - Alf Jan 15 '11 at 8:50
@Alf: Can you please provide a more in pdeth explanation please. –  Matthieu N. Jan 15 '11 at 9:15
show 1 more comment

2 Answers

You may have some success with combinatorial numbers, which allow you to retrieve the N'th (n/10th) k-combination with a simple algorithm; then run the next_combination algorithm n/10 times on each of the ten nodes to iterate.

Sample code (in C#, but quite readable for a C++ programmer) can be found on MSDN.

share|improve this answer
The James McCaffrey article, where he describes a method to get the Nth combination is too expensive. Using next_combination (links) mutates the original range, perhaps something that can determine what the range looks like at the Nth combination, because one could pass that specific range to a compute node. –  Matthieu N. Jan 15 '11 at 9:20
Why is it too expensive? You only need to run this 10 times on the master, then run next_combination on the compute nodes. –  larsmans Jan 15 '11 at 9:46
@Reyzooti: if you have an index-based thing, then turning it into a RandomAccessIterator is easy --> keep a pointer to the sequence and an index in the iterator :) –  Matthieu M. Jan 15 '11 at 13:04
What's with the downvoting? –  larsmans Feb 23 '11 at 10:01
add comment

Have node number n process every tenth combination, starting from the nth.

share|improve this answer
Still requires each node to iterate over every n-choose-k combos, which results in 90% iteration redudancy per node, less overhead than the master node solution however still more than distributing ranges of combinations. –  Matthieu N. Jan 15 '11 at 9:14
add comment

Your Answer

