comment on

Thanks for the post, Sorry for my late reply -- works been busy, and my "client" (aka: my girlfriend) has been too busy grading finals to discuss how she really wants it to work, and what kind of "scoring" she wants to apply to permutations.

Your approach is really cool (that reduce call is psycho by the way) but it doesn't seem to do very well in some simple cases.

By iterating over "0 .. $maxChoices" at the core, and assigning people to sections as early as it can, it produces a lot of solutions in which people are left out of sections, even if another solution exists in which they do get into a section at the expense of someone else getting their second choice instead of their first. (It's definitely important to pay attention to people's prefrences, but a solution in which everyone gets their last choice is definitely better then a solution in which 90% of people get their first choice, and the other 10% don't get anything)...

laptop:~/tmp> pm-node-411417-sectionassignments.pl -STUDENTS=5 -SECTIONS=3
Sections: 3 
        available Section_00 =>1
        available Section_01 =>2
        available Section_02 =>2
Students: 5 [
        Student_00      [ 1 2 ], 
        Student_01      [ 0 1 ], 
        Student_02      [ 0 ], 
        Student_03      [ 0 2 ], 
        Student_04      [ 1 2 ]
]
Sect:Section_01; avail: 2       [0 4][]
Alloc1:                         [0 4][0 4]
Sect:Section_00; avail: 1       [1 2 3][0 4]
lastchoice:             [2]
Alloc2:                         [1 3][0 2 4]
left: Student_01 Student_03
Sect:Section_01; avail: 0       [0][]
lastchoice:             [0]
Sect:Section_02; avail: 2       [1][]
Alloc1:                         [1][1]
left: Student_01
left: Student_01
Section_00(0) => [ Student_02 ]
Section_01(0) => [ Student_00 Student_04 ]
Section_02(1) => [ Student_03 ]

Unallocated; [Student_01]

(if Student_04 is moved to Section_02, Student_01 can be in Section_01)

laptop:~/tmp> pm-node-411417-sectionassignments.pl -STUDENTS=5 -SECTIONS=3
Sections: 3 
        available Section_00 =>0
        available Section_01 =>3
        available Section_02 =>2
Students: 5 [
        Student_00      [ 0 1 2 ], 
        Student_01      [ 1 2 0 ], 
        Student_02      [ 1 0 ], 
        Student_03      [ 1 ], 
        Student_04      [ 0 1 ]
]
Sect:Section_01; avail: 3       [1 2 3][]
Alloc1:                         [1 2 3][1 2 3]
Sect:Section_00; avail: 0       [0 4][1 2 3]
lastchoice:             []
left: Student_00 Student_04
Sect:Section_01; avail: 0       [0 1][]
lastchoice:             [1]
left: Student_00 Student_04
Sect:Section_02; avail: 2       [0][]
Alloc1:                         [0][0]
left: Student_04
left: Student_04
Section_00(0) => [EMPTY]
Section_01(0) => [ Student_03 Student_02 Student_01 ]
Section_02(1) => [ Student_00 ]

Unallocated; [Student_04]

(if we move Student_01 to Section_02 then Student_04 can fit in Section_01 )

Unfortunately, I don't see an easy way to fix this. A "try it several times and pick the best run" won't do much good, since randomness isn't even a factor in these problem cases (the "Alloc1" and "Alloc2" allocations are deterministic)

Thoughts?

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

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Keep It Simple, Stupid
	PerlMonks