Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

Re^2: [OT] simple algorithm for assigning students to class sections

by hossman (Prior)
on Nov 30, 2004 at 18:50 UTC ( #411244=note: print w/replies, xml ) Need Help??

in reply to Re: [OT] simple algorithm for assigning students to class sections
in thread [OT] simple algorithm for assigning students to class sections

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?

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;

  1. An approach like that would give an advantage to people who only listed one choice, while other people who tried to be flexible would get penalized for the "greater good"
  2. Even discounting that point, there could be lots of solutions in which the same number of people get matched to a section, so what's a good tie breaker in those cases?

(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)


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...

%students = (studentA => [sec3, sec1, sec2], studentB => [sec1], studentC => [sec4, sec3, sec1], studentD => [sec2, sec3], studentE => [sec2, sec4, sec3, sec1], ...);

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?)

  • Comment on Re^2: [OT] simple algorithm for assigning students to class sections
  • Download Code

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://411244]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2021-01-16 10:48 GMT
Find Nodes?
    Voting Booth?