perlquestion
hossman
<p>
Does anyone know of a nice simple algorithm (Or better yet: a perl implimentation) for picking which students should be in which sections, based on the preferences of the students?
</p>
<p>
There's lots of discussions about "Matching Algorithms" out there, but most of them either address the "Stable Marriage" problem (a one-to-one mapping where the men and women all express prefrences) or the "Hospitals/Residents" problem (a many-to-one mapping where the doctors and hospitals all express prefrences)
</p>
<p>
What I'm looking for, is a many-to-one solution where only the students express their prefrences, and the class sections specify a max number of allowed students (which may vary by section). Something like...
</p>
<code>
%sections = (sec1 => 2, sec2 => 4, sec3 => 4, sec4 => 3, ...);
%students = (studentA => [sec3, sec1, sec2],
studentB => [sec1],
studentC => [sec4, sec3, sec1],
studentD => [sec2, sec3],
studentE => [sec2, sec4, sec3, sec1],
...);
%matches = best_permutation(\%sections, \%students);
</code>
<p>
suggestions?
</p>