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);
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||