note
hossman
<p>
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.
</p>
<p>
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.
</p>
<p>
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)...
</p>
<readmore>
<pre>
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]
</pre>
<i>(if Student_04 is moved to Section_02, Student_01 can be in Section_01)</i>
<pre>
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]
</pre>
<i>(if we move Student_01 to Section_02 then Student_04 can fit in Section_01 )</i>
</readmore>
<p>
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)
</p>
<p>
Thoughts?
</p>
411129
411417