<br><div><span class="gmail_quote">On 10/22/07, <b class="gmail_sendername">manu</b> <<a href="mailto:firstname.lastname@example.org">email@example.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello<br><br>I am not sure it is appropriate to post to this mailing list to<br>inquire about a peculiar algorithm, if not let me know...<br><br>I was looking at one particular puzzle posted on the Facebook site,<br>'Wiretaps' (
<a href="http://www.facebook.com/jobs_puzzles/?puzzle_id=11">http://www.facebook.com/jobs_puzzles/?puzzle_id=11</a>).<br>Briefly, you have 26 programmers (numbers 1 to 26) which need to be<br>assigned a job (a name to decode).
<br>Even numbered programmers spend 1.5 hours more per vowel. Odd ones<br>spend 1 hour more per consonant. And finally, each programmer whose<br>number share primes factors with the length of the name to decode,<br>spend 2 hours extra per factor (For example, it takes programmer 12
<br>-- factors of 2 and 3 -- an extra 4 hours to decode 'NORMAN')<br><br>The point is to come up with the combination of (programmer, name)<br>which minimizes the time taken overall.<br><br>Now the simplest solution, conceptually, is calculating the time
<br>taken by each combination, and pick the fastest...<br>However looking at the number of permutations (26! =<br>403291461126605635584000000), quickly dampened my enthusiasm...<br><br>There must be some algorithm (dynamic programming ?), that cuts down
<br>the number of calculations involved in order to find the right<br>combination. But I cannot identify the proper algorithm to use...<br><br>Can someone give me a tip ? Can some of the computations be<br>parallelized ?<br>
<br>(it's not an assignment, nor will I send anything to Facebook, I am<br>just trying this out of curiosity)<br><br>Thank you</blockquote><div><br>This is an instance of what is known as the <a href="http://en.wikipedia.org/wiki/Assignment_problem">
assignment problem</a> -- to find a maximum/minimum weight perfect matching, given a weighted bipartite graph. It can be solved by the <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm">Hungarian Algorithm</a>. You can also read about
<a href="http://en.wikipedia.org/wiki/Matching">matchings</a> in general; there are also other algorithms than the Hungarian which might be somewhat less optimal but still fine for your purposes and perhaps easier to code.