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
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |