I have to match a list managers and their preferred schools. Each manager will write down their top 5 favorite schools (in order). There are 24 managers and 12 schools; each school gets two managers.
This is the sorting logic I used, but it doesn't seem to work:
Randomly assign 2 managers to each school.
Calculate the initial total preference, P.
Create an array of all managers
While managers is not empty:
Select the first manager, m
Determine its current assigned university, u'
Determine its top preferred university, u
Determine the least preferred manager for u, m'
Try to switch these two managers ( m->u, m'->u')
Calculate the new preference, P'
If( P' > P )
Accept the switch
Push the manager, m' to the manager array list
EndIf
EndWhile
The PHP code I have written is:
// Assume $this->managers has the list of all managers, and $this->universities has the list of universities
// Managers are already assigned to the universities
$managers = $this->managers;
shuffle($managers);
while( !empty($managers) )
{
// Select the Manager
$m = array_shift($managers);
// Find school they are part of
$current = $this->getCurrentUniversity($m);
// Find their top school
$top = $this->getTopUniversity($m, $current);
// Find least preferred person for $top
$least = $this->getLeastManager($top);
$try = $this->switchManagers($m, $current, $top, $least);
// If this makes it better, then accept it!
$tryPref = $this->preference($try);
if( $tryPref > $preference ) {
$this->universities = $try;
$preference = $tryPref;
array_push($managers, $least);
}
}
Needless to say, it doesn't work. It does make the match relatively better, but it is not the best sorting. More over, if rerun the program, everytime I get a new result. So the matching is not converging and there is no unique answer.
Why?!