Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
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?)

In reply to Re^2: [OT] simple algorithm for assigning students to class sections by hossman
in thread [OT] simple algorithm for assigning students to class sections by hossman

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • 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:
    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
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others taking refuge in the Monastery: (4)
    As of 2021-01-16 11:02 GMT
    Find Nodes?
      Voting Booth?