[Haskell-cafe] What algorithm to use ?

[Brent Yorgey]

On 10/22/07, manu <emmanuel.delaborde at citycampus.com> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071022/1d9d3e54/attachment.htm