[Haskell-cafe] What algorithm to use ?

Brent Yorgey byorgey at gmail.com
Mon Oct 22 07:01:04 EDT 2007

```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,
> 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>.