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?
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)
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...
%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);