hossman has asked for the wisdom of the Perl Monks concerning the following question:
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);
suggestions?
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: [OT] simple algorithm for assigning students to class sections
by kvale (Monsignor) on Nov 30, 2004 at 09:37 UTC | |
To do better than this simple lottery scheme, you must first decide what your optimality critera are. Do you want to maximize the number of first choices satisfied? The number of any choice satisfied? -Mark | [reply] |
by aquarium (Curate) on Nov 30, 2004 at 13:00 UTC | |
the hardest line to type correctly is: stty erase ^H
| [reply] |
by traveler (Parson) on Nov 30, 2004 at 16:43 UTC | |
Just some thoughts to get you started tinking... | [reply] |
by hossman (Prior) on Nov 30, 2004 at 18:50 UTC | |
See, that's part of my problem. I was asked to try and find a way to "get everyone in a section they can make" (ie: if they can't make it, they didn't list it in their prefrences) without any other critera. Which means a naive lottery like you described would work fine, assuming I just kept doing lots of iterations (using a different initial order of students) and picking the "best" based on which solution results in the fewest number of people left out of a section. But it seems to me that there are still two problems; (I think the biggest part of my problem is that I'm not sure what the optimal criteria are ... which is why I'm hoping someone would have pointers to algorithms other people have used in problems like this -- where one side of the match only cares about quantity, not quality) UPDATE:An idea just occured to me. I could score the solutions based on the sum of the "rank" of the choice each of section each student was assigned to. or to use an example, given the following prefrences...
A solution in which studentA was put in sec3 would get 3 points, because he listed 3 prefrences and got his first one. putting studentB in sec1 would only be worth 1 point, because he only listed one choice. Putting studentE in sec1 would be worth 1 point (because it was his last choice) but putting him in sec2 would be worth 4 points because it was his first (of 4) choice. if someone doesn't get placed in a section at all, the solution doesn't earn a point for them. That seems like it would give priority to finding every one a section, but would be somewhat fair to people who were flexible, right? The only problem I see right now, is that if there were two solutions that differed only in the order of processing studentB and studentE, and sec2,sec3,sec4 were already full and sec1 only had one spot left, then there would still be a tie between the solutions, even though studentE had been more flexible and (in my mind) deserves the slot more. Maybe a solution in which someone doesn't get into any section should have the k*n points removed from it's score (where k is some small constant and n is hte number of prefrences the student listed?) | [reply] [d/l] |
Re: [OT] simple algorithm for assigning students to class sections
by BrowserUk (Patriarch) on Nov 30, 2004 at 17:20 UTC | |
A few questions: Examine what is said, not who speaks.
"But you should never overestimate the ingenuity of the sceptics to come up with a counter-argument." -Myles Allen"Think for yourself!" - Abigail "Time is a poor substitute for thought"--theorbtwo "Efficiency is intelligent laziness." -David Dunham "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon | [reply] |
by hossman (Prior) on Nov 30, 2004 at 19:04 UTC | |
I'm not adverse to using a brute force approach and letting it churn for a few hours. I'm just not sure what the best brute force approach is, or how to decide when one solution is "better" then another.
| [reply] |
by BrowserUk (Patriarch) on Dec 01, 2004 at 09:27 UTC | |
Have a play with this and see how you get on. Update: Corrected error in output code to display [EMPTY] if a course ends up with no students. Uncommented and improved format of output.
Output:
Examine what is said, not who speaks.
"But you should never overestimate the ingenuity of the sceptics to come up with a counter-argument." -Myles Allen"Think for yourself!" - Abigail "Time is a poor substitute for thought"--theorbtwo "Efficiency is intelligent laziness." -David Dunham "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon | [reply] [d/l] [select] |
by hossman (Prior) on Dec 05, 2004 at 02:10 UTC | |
by BrowserUk (Patriarch) on Dec 05, 2004 at 07:53 UTC | |
| |
by Zero_Flop (Pilgrim) on Dec 01, 2004 at 05:24 UTC | |
| [reply] |
Re: [OT] simple algorithm for assigning students to class sections
by mattr (Curate) on Dec 01, 2004 at 15:17 UTC | |
1. I'm not sure it's ethical to give "flexible" people more weight. It is a lottery, and the choices are based on what classes they are physically able to attend. 2nd, 3rd choices are decisions based on the scenario on what if I fail to get my wish, which is different from being flexible. So I think you should try to get everyone their first choices and see which courses are oversubscribed. Then run a lottery for the busy courses. People who lose the lottery get second choice if possible, and if they have no other choices they get either no course, a random choice, or a list of remaining courses for which they can apply. Another possibility is you can leave a few seats in busy courses free and decide in a second round who to put into them based on other considerations. I also think it might be a good idea to try and develop other considerations to reduce the number of people vying for a popular course, such as their year in college, their academic credentials, their major, etc. I am not at all for it but if you want female engineers there's that too. 2. A voice spoke to me and said "simulated annealing". Which I always thought would be interesting to investigate but never had a reason. It is another way to solve these things, and there is a related algorithm called the Metropolis algorithm (google annealing and scheduling). It is based on a slowly cooling metal that crystallizes with minimum energy disparities and tunnels out of local minima, and is useful for traveling salesman type problems. In other words if you can model this in terms of energy and geometrical relationships this might be a good one. But it seems hard to me to see what is going on and hard to ensure human considerations like the above. Incidentally I was googling (school scheduling algorithm) and then added the term "annealing". Turns out that is what Syracuse University used, I just found out, for their NP hard timetabling problem. (See the PDF) They are mixing in some neurons too, it is pretty serious stuff. They are calling certain classes "high cost" and looking for scheduling conflicts, etc. which is more than what you need. So you will have to model differently or use a subset of what they do. As noted on p. 16 of the pdf, it includes student preferences. Some good news perhaps is that the GNU Scientific Library has a simulated annealing function def called gsl_siman_solve which might be usable from the Perl module Math::GSL::Sf. There are other perl annealing modules (search cpan) and it turns out the Perl Mongers world map used an Inline::C annealing routine (until a year ago) (in Image::WorldMap to keep labels from overlapping) too! (See bottom for link about the algorithm used now,) Bioperl also uses it. You might like to check out Algorithm::Evolutionary which provides both annealing and roulette wheels. Anyway this looks like a very useful thing to have in Perl for a lot of things so I would like to learn how to use it better. FWIW I also found an overview of scheduling algorithms, this is an exciting (to me anyway) area that is well researched, and aside from annealing I understand "list-based" algorithms are used to manage limited resources however this was in the context of chip development. Anyway this may be overkill but I think if you have more restrictions then simulated annealing is a) the only way to stay sane, b) competitive with other heuristics (so they say), and c) going to give you close to the best possible results. Oh and it takes a looong time to run so you will be happy about that part maybe. The pdf mentions a comparison between graph coloring (as a fast heuristic) instead of a rule-based preprocessor, which sounds like what someone mentioned earlier.
Other links:
| [reply] |
Re: [OT] simple algorithm for assigning students to class sections
by exussum0 (Vicar) on Nov 30, 2004 at 14:19 UTC | |
Update: as for limiting the amount of people with the same class/colour, you can do that progrematically. Once a colour is all used up, use a new one by force.
---- | [reply] |
Re: [OT] simple algorithm for assigning students to class sections
by Anonymous Monk on Nov 30, 2004 at 09:29 UTC | |
| [reply] |