From: MikkelFJ <mikkelfj-anti-spam@...>
Date: 2002-08-06T18:20:53+09:00
Subject: Re: Coding challenge (on Ruby Garden)


"David Alan Black" <dblack@candle.superlink.net> wrote in message
news:Pine.LNX.4.30.0208052056270.15880-100000@candle.superlink.net...
> Hello --
>
> Coding Challenge 0002 (my numbering scheme :-) has been posted to
> <http://www.rubygarden.org/ruby?CodingChallenge0002>.
>
....
> This would return true:
>
>    [1,2,3]
>    [ [1,11,111], [0,3,2], [2,4,6] ]

This is actually a special case of the assignment problem of operational
analysis.

You have M machines and M jobs. Each machine needs to be assigned a job. In
this case there is no preference to the quality of assignments, in the
classical case you assign a cost for each job on a given machine. In this
case the cost is either infinite of the machine cannot handle the job, or 0
if it can.

You can view the numbers in the first array as Job Id's and the second array
as the ability of a machine to handle a given job.

You can represent a M x M matrix of the problem for the above example where
each row is a Job Id and each column is a machine.

For the given example:
>    [1,2,3]
>    [ [1,11,111], [0,3,2], [2,4,6] ]

you get

[[ 0, inf, inf],  (Job 1 on each machine)
 [ inf, 0, 0],   (Job 2 on each machine)
 [ inf, 0, inf]] (Job 3 on each machine)


Mikkel