On 10/22/07, manu <[EMAIL PROTECTED]> wrote: > > Hello > > I am not sure it is appropriate to post to this mailing list to > inquire about a peculiar algorithm, if not let me know... > > I was looking at one particular puzzle posted on the Facebook site, > 'Wiretaps' (http://www.facebook.com/jobs_puzzles/?puzzle_id=11). > Briefly, you have 26 programmers (numbers 1 to 26) which need to be > assigned a job (a name to decode). > Even numbered programmers spend 1.5 hours more per vowel. Odd ones > spend 1 hour more per consonant. And finally, each programmer whose > number share primes factors with the length of the name to decode, > spend 2 hours extra per factor (For example, it takes programmer 12 > -- factors of 2 and 3 -- an extra 4 hours to decode 'NORMAN') > > The point is to come up with the combination of (programmer, name) > which minimizes the time taken overall. > > Now the simplest solution, conceptually, is calculating the time > taken by each combination, and pick the fastest... > However looking at the number of permutations (26! = > 403291461126605635584000000), quickly dampened my enthusiasm... > > There must be some algorithm (dynamic programming ?), that cuts down > the number of calculations involved in order to find the right > combination. But I cannot identify the proper algorithm to use... > > Can someone give me a tip ? Can some of the computations be > parallelized ? > > (it's not an assignment, nor will I send anything to Facebook, I am > just trying this out of curiosity) > > Thank you
This is an instance of what is known as the assignment problem<http://en.wikipedia.org/wiki/Assignment_problem>-- to find a maximum/minimum weight perfect matching, given a weighted bipartite graph. It can be solved by the Hungarian Algorithm<http://en.wikipedia.org/wiki/Hungarian_algorithm>. You can also read about matchings <http://en.wikipedia.org/wiki/Matching> 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. -Brent
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe