http://qs321.pair.com?node_id=412851


in reply to Re^5: [OT] simple algorithm for assigning students to class sections
in thread [OT] simple algorithm for assigning students to class sections

Yes. You need a Jiggle® :)

Wow ... that's pretty cool. But, I'm worried that the general strategy is too vulnerable to "local maximum" ... the Jiggle helps, but as you found with your "-R=847" example: a single level isn't allways enough.

I also found some examples like this one below that it didn't catch (which seems weird to me, because only Student_003 needs to be shifted to make it work, but for some reason it didn't try that one -- the code looks like it should have, but I didn't debug it to figure out why it didn't)

laptop:~/tmp> ./pm-node-412469-sectionassignments.pl -STUDENTS=5 -SECT +IONS=3 -R=9 !9! Sections: 3 available Section_000 =>3 available Section_001 =>1 available Section_002 =>1 Students: 5 [ Student_000 [ 0 2 1 ], Student_001 [ 1 ], Student_002 [ 1 2 ], Student_003 [ 2 0 ], Student_004 [ 1 0 ] ] Unallocated after main pass; [Student_002] Sections with places: [Section_000] looking at placed student Student_000 looking at placed student Student_004 Failed to replace Student_002 Unallocated after one-level jiggle(TM); [Student_002] Section_000(1) => [ Student_000 Student_004 ] Section_001(0) => [ Student_001 ] Section_002(0) => [ Student_003 ]

The more I look at datasets where someone gets left out, it seems like processing the stdudents in ascending order of prefrence size (breaking ties in ascending order space available in their first choice section) might be the best way to minimize the number of solutions that have people leftover. (of course, you have to constantly resort as sections fill up)

Another idea I got after looking at your first algorithm, was that one way to try and improve on a solution with leftovers would be to use something like the following psuedo-code...

# solution = browserUK(sections, students); # if (solution->leftout()) { # round1 = solution->leftout(); # round2 = students - round1; # sol = browserUK(sections, round1); # solution = browserUK(sol->sections(), round2); # } # return $solution;

(ie: try to divide the problem up by getting the leftovers in first)

Depending on how much time i wind up having to crank this out, I think I'll try to impliment the "fewest picks first" function, and a lottery based function, and wrap your approach in a function with the same API; so I can then make a generic wrapper that can run all three, compare their output, and then (assumign leftovers) generate all the possible solutions from having each algorithm "narrow" the problem for the others by alocating their leftovers first.

I'll keep you posted