Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Re^4: [OT] simple algorithm for assigning students to class sections

by hossman (Prior)
on Dec 05, 2004 at 02:10 UTC ( #412449=note: print w/replies, xml ) Need Help??


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

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?

  • Comment on Re^4: [OT] simple algorithm for assigning students to class sections

Replies are listed 'Best First'.
Re^5: [OT] simple algorithm for assigning students to class sections
by BrowserUk (Pope) on Dec 05, 2004 at 07:53 UTC
    Thoughts?

    Yes. You need a Jiggle® :)

    1. For each unallocated student's choices
    2. For each student currently allocated to that choice.
    3. For each of their alternate choices
    4. If that alternate has spaces
    5. Swap the unallocated student with the allocated student, and assign the previously placed student into the section with places available.
    6. Repeat until everyone is allocated; or you gave it your best shot.

    Of course, that doesn't guarentee a solution, but it seems to do remarkably well if a solution is possible.

    I couldn't reproduce your exact example (without hard coding it) but I found a couple of similar one that the above Jiggle solves:

    [ 7:13:08.03] P:\test>411129.pl -STUDENTS=5 -SECTIONS=3 -R=473 Use of uninitialized value in sprintf at P:\test\411129.pl line 121. !473! Sections: 3 available Section_000 =>2 available Section_001 =>2 available Section_002 =>1 Students: 5 [ Student_000 [ 1 2 ], Student_001 [ 2 ], Student_002 [ 0 ], Student_003 [ 0 2 1 ], Student_004 [ 2 0 ] ] Unallocated after main pass; [Student_004] Sections with places: [Section_001] looking at placed student Student_002 looking at placed student Student_003 moved Student_003 to Section_001 and put Student_004 in Section_000 Unallocated after one-level jiggle(TM); [] Section_000(0) => [ Student_004 Student_002 ] Section_001(0) => [ Student_000 Student_003 ] Section_002(0) => [ Student_001 ] [ 7:27:12.45] P:\test>411129.pl -STUDENTS=5 -SECTIONS=3 -R=114 Use of uninitialized value in sprintf at P:\test\411129.pl line 121. !114! Sections: 3 available Section_000 =>2 available Section_001 =>2 available Section_002 =>1 Students: 5 [ Student_000 [ 1 2 0 ], Student_001 [ 0 ], Student_002 [ 2 1 ], Student_003 [ 0 2 1 ], Student_004 [ 0 2 ] ] Unallocated after main pass; [Student_004] Sections with places: [Section_001] looking at placed student Student_001 looking at placed student Student_003 moved Student_003 to Section_001 and put Student_004 in Section_000 Unallocated after one-level jiggle(TM); [] Section_000(0) => [ Student_004 Student_001 ] Section_001(0) => [ Student_000 Student_003 ] Section_002(0) => [ Student_002 ]

    And one which it didn't, but I don't thinkhas a solution with a one-level Jiggle?:

    [ 7:27:22.42] P:\test>411129.pl -STUDENTS=5 -SECTIONS=3 -R=847 !847! Sections: 3 available Section_000 =>3 available Section_001 =>1 available Section_002 =>1 Students: 5 [ Student_000 [ 0 1 ], Student_001 [ 1 2 0 ], Student_002 [ 2 1 ], Student_003 [ 2 ], 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 ]

    It also seems to work pretty well on much larger tasks (Output substantially trimmed to show just those affected by the jiggle:

    Of course, you could code a 2-level Jiggle fairly easily, and you could go on to try for a recursive Jiggle. Though I think that it might be better to simply rotate the displaced students through the @students array until a solution is found (if possible).

    Regardless, the Jiggle seems to solve most solvable runs I've tried almost immediately, so it would need a solvable example, that it didn't find a solution for, before the extra effort would be worthwhile.

    The main body of the code is unchanged except I made the generator a little less prone to producing insoluble datasets.

    The Jiggle code is the at the end. It's fairly well commented. It uses a couple of discuised gotos (next/last on the outer loop) and a crude sentinel to break the infinite loop possibility with insoluable datasets. It could be better structured, but try it and see what you think?

    PS. Sorry for leaving PM to do the wrapping -- it's been a long night :)


    Examine what is said, not who speaks.
    "But you should never overestimate the ingenuity of the sceptics to come up with a counter-argument." -Myles Allen
    "Think for yourself!" - Abigail        "Time is a poor substitute for thought"--theorbtwo         "Efficiency is intelligent laziness." -David Dunham
    "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
      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)

      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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://412449]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (4)
As of 2021-01-26 19:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?