good chemistry is complicated,and a little bit messy -LW PerlMonks

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

by kvale (Monsignor)
 on Nov 30, 2004 at 09:37 UTC ( #411140=note: print w/replies, xml ) Need Help??

A simple, fair algorithm would be to draw students from the pool, one at a time without replacement. For each student, put them into their first choice section, if it is not full. If the first choice is full, try the second, and so on. If all the choices are full, pick the section with the greatest number of empty spaces.

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

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

Replies are listed 'Best First'.
Re^2: [OT] simple algorithm for assigning students to class sections
by aquarium (Curate) on Nov 30, 2004 at 13:00 UTC
i second the above comment...as the criteria that the school would most likely want is: NOT lots of classes with few students in them. Management might even like to try for: overseas full-fee paying students always get first pick at preferences. Good luck :)
the hardest line to type correctly is: stty erase ^H
Re^2: [OT] simple algorithm for assigning students to class sections
by traveler (Parson) on Nov 30, 2004 at 16:43 UTC
You may also want to visit some other constraints and "pathalogical cases". e.g. Is it important that sections have the approximately the same size? If so, is giving a student his or her first choice more or less important than keeping sizes similar? What if everyone prefers section 1 as a first choice, 2 as a second, etc? Is the aforementioned lottery "fair" or, as is noted below, are there other criteria applied to give particular students' choices greater weight?

Just some thoughts to get you started tinking...

Re^2: [OT] simple algorithm for assigning students to class sections
by hossman (Prior) on Nov 30, 2004 at 18:50 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?

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)

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

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

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

Log In?
 Username: Password:

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

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (3)
As of 2021-06-21 03:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What does the "s" stand for in "perls"? (Whence perls)

Results (97 votes). Check out past polls.

Notices?