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


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

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 ]

[download]

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 ]

[download]

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

[ 7:29:09.00] P:\test>411129.pl -STUDENTS=750 -SECTIONS=20 -R=157
Use of uninitialized value in sprintf at P:\test\411129.pl line 121.
!157!
Sections: 20
        available Section_000 =>33
        available Section_001 =>33
        available Section_002 =>37
        available Section_003 =>40
        available Section_004 =>49
        available Section_005 =>46
        available Section_006 =>37
        available Section_007 =>36
        available Section_008 =>38
        available Section_009 =>35
        available Section_010 =>43
        available Section_011 =>36
        available Section_012 =>50
        available Section_013 =>39
        available Section_014 =>29
        available Section_015 =>27
        available Section_016 =>37
        available Section_017 =>43
        available Section_018 =>32
        available Section_019 =>30
Students: 750 [
...
        Student_053     [ 14 9 3 13 16 1 5 19 7 18 10 0 11 2 4 ],
...
        Student_092     [ 0 10 5 2 12 4 15 14 18 17 ],
...
        Student_156     [ 0 4 19 10 14 11 1 12 3 ],
...
        Student_164     [ 15 7 ],
...
        Student_197     [ 0 19 14 8 12 1 ],
...
        Student_232     [ 0 18 15 19 1 12 2 ],
...
        Student_286     [ 14 15 13 3 10 19 9 18 1 8 2 12 16 4 11 17 5 
+0 7 6 ],
...
        Student_331     [ 9 14 16 1 7 15 8 19 18 ],
...
        Student_555     [ 19 9 6 ],
...
        Student_673     [ 15 6 ],
...
]

Unallocated after main pass; [Student_053 Student_164 Student_331 Stud
+ent_555 Student_673]
Sections with places: [Section_012]

looking at placed student Student_264
looking at placed student Student_330
looking at placed student Student_050
looking at placed student Student_211
looking at placed student Student_542
looking at placed student Student_191
looking at placed student Student_213
looking at placed student Student_516
looking at placed student Student_197
moved Student_197 to Section_012 and put Student_053 in Section_000

looking at placed student Student_053
looking at placed student Student_264
looking at placed student Student_330
looking at placed student Student_050
looking at placed student Student_211
looking at placed student Student_542
looking at placed student Student_191
looking at placed student Student_213
looking at placed student Student_516
looking at placed student Student_239
looking at placed student Student_417
looking at placed student Student_232
moved Student_232 to Section_012 and put Student_164 in Section_000

looking at placed student Student_164
looking at placed student Student_053
looking at placed student Student_264
looking at placed student Student_330
looking at placed student Student_050
looking at placed student Student_211
looking at placed student Student_542
looking at placed student Student_191
looking at placed student Student_213
looking at placed student Student_516
looking at placed student Student_239
looking at placed student Student_417
looking at placed student Student_335
looking at placed student Student_561
looking at placed student Student_059
looking at placed student Student_156
moved Student_156 to Section_012 and put Student_331 in Section_000

looking at placed student Student_331
looking at placed student Student_164
looking at placed student Student_053
looking at placed student Student_264
looking at placed student Student_330
looking at placed student Student_050
looking at placed student Student_211
looking at placed student Student_542
looking at placed student Student_191
looking at placed student Student_213
looking at placed student Student_516
looking at placed student Student_239
looking at placed student Student_417
looking at placed student Student_335
looking at placed student Student_561
looking at placed student Student_059
looking at placed student Student_092
moved Student_092 to Section_012 and put Student_555 in Section_000

looking at placed student Student_555
looking at placed student Student_331
looking at placed student Student_164
looking at placed student Student_053
looking at placed student Student_264
looking at placed student Student_330
looking at placed student Student_050
looking at placed student Student_211
looking at placed student Student_542
looking at placed student Student_191
looking at placed student Student_213
looking at placed student Student_516
looking at placed student Student_239
looking at placed student Student_417
looking at placed student Student_335
looking at placed student Student_561
looking at placed student Student_059
looking at placed student Student_283
moved Student_283 to Section_012 and put Student_673 in Section_000


Unallocated after one-level jiggle(TM); []
Section_000(0) => [ Student_673 Student_555 Student_331 ...
Section_001(0) => [ Student_529 Student_617 Student_674 ...
Section_002(0) => [ Student_387 Student_676 Student_049 ...
Section_003(0) => [ Student_502 Student_006 Student_081 ...
Section_004(0) => [ Student_423 Student_479 Student_547 ...
Section_005(0) => [ Student_055 Student_157 Student_241 ...
Section_006(0) => [ Student_093 Student_327 Student_251 ...
Section_007(0) => [ Student_124 Student_305 Student_558 ...
Section_008(0) => [ Student_042 Student_111 Student_271 ...
Section_009(0) => [ Student_664 Student_699 Student_301 ...
Section_010(0) => [ Student_467 Student_598 Student_693 ...
Section_011(0) => [ Student_734 Student_038 Student_657 ...
Section_012(0) => [ Student_095 Student_106 Student_137 ...
Section_013(0) => [ Student_578 Student_725 Student_541 ...
Section_014(0) => [ Student_596 Student_215 Student_044 ...
Section_015(0) => [ Student_196 Student_571 Student_718 ...
Section_016(0) => [ Student_183 Student_010 Student_367 ...
Section_017(0) => [ Student_048 Student_293 Student_041 ...
Section_018(0) => [ Student_312 Student_208 Student_140 ...
Section_019(0) => [ Student_009 Student_034 Student_107 ...

[ 7:30:51.95] P:\test>

[download]

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? 

#! perl -slw
use strict;
use List::Util qw[ shuffle max min reduce sum first ];

our $SECTIONS   ||= 15;
our $STUDENTS   ||= 50;
our $MAXCHOICE  ||= $SECTIONS;
our $R ||= int rand 1000;
print "!$R!";
srand( $R );

## Gen some test data
my %sections = map{; 
    sprintf( "Section_%03d", $_ )  
    => 
    {available => 1 } 
} 0 .. $SECTIONS - 1;

my @sections = sort keys %sections;
my $n = $STUDENTS - $SECTIONS;
$sections{ $sections[ rand @sections ] }{ available }++ 
    while $n--;

printf "Sections: %d \n\t%s\n", scalar keys %sections, join "\n\t", 
    map{ join " $_ =>", %{ $sections{ $_ } } } @sections;

my %students = map{ 
    my $prefs = 1+int( rand $MAXCHOICE );
    sprintf( "Student_%03d", $_ )
    => 
    [ ( shuffle( 0 .. $SECTIONS-1 ) )[ 0 .. $prefs-1 ] ]
} 0 .. $STUDENTS-1;
my @students = sort keys %students;

printf "Students: %d [%s\n]\n", scalar keys %students, 
    join ', ', map{ "\n\t$_\t[ @{ $students{ $_ } } ]" } @students;


## Main algorithm


my $maxChoices = max( map{ scalar @{ $students{ $_ } } } @students );
for my $choice ( 0 .. $maxChoices ) {
    my $byChoice  = reduce{
        push @{ $a }, [] 
            if defined $a->[ -1 ][ 0 ]
            and ( $students{ $students[ $a->[ -1 ][ 0 ] ] }[ $choice ]
+||1e99 ) 
             != ( $students{ $students[ $b ]              }[ $choice ]
+||1e99 ) ;
        push @{ $a->[ -1 ] }, $b;
        $a
    } [[]], sort{ 
        ($students{ $students[ $a ] }[ $choice ]||99999) <=> ($student
+s{ $students[ $b ] }[ $choice ]||99999) ## By nth choice
    or
        @{ $students{ $students[ $a ] } } <=> @{ $students{ $students[
+ $b ] } }             ## or number of choices
    } 0 .. $#students;
    
    my @allocated;
    for my $chose ( @$byChoice ) {
        next unless defined $students{ $students[ $chose->[ -1 ] ] }[ 
+$choice ];
        my $section = sprintf "Section_%03d", 
            $students{ $students[ $chose->[ -1 ] ] }[ $choice ];
            
#        print "Sect:$section; avail: $sections{ $section }{ available
+ }\t[@{[ sort {$a<=>$b} @$chose ]}][@{[ sort {$a<=>$b} @allocated ]}]
+";
        
        if( @$chose <= $sections{ $section }{ available }  ) { 
            push @{ $sections{ $section }{ allocated } }, @students[ @
+$chose ];
            $sections{ $section }{ available } -= @$chose;
            push @allocated, @$chose;
#            print "Alloc1: \t\t\t[@{[ sort {$a<=>$b} @$chose ]}][@{[ 
+sort {$a<=>$b} @allocated ]}]";
            next;
        }
        
        my @lastChoice = grep{ 
            $#{ $students{ $students[ $_ ] } } == $choice 
        } @$chose;
        
#        print "lastchoice: \t\t[@lastChoice]";
        
        if( @lastChoice and @lastChoice <= $sections{ $section }{ avai
+lable } ) {
            push @{ $sections{ $section }{ allocated } }, @students[ @
+lastChoice ];
            $sections{ $section }{ available } -= @lastChoice;
            @{ $chose } = grep{ 
                my $allocated = $_;
                !grep{ $_ == $allocated } @lastChoice
            } @$chose;
            push @allocated, @lastChoice;
#            print "Alloc2: \t\t\t[@{[ sort {$a<=>$b} @$chose ]}][@{[ 
+sort {$a<=>$b} @allocated ]}]";
        }
        
        if( @$chose and $sections{ $section }{ available } ) {
            my @random = ( shuffle( @$chose ) )[ 0 .. $sections{ $sect
+ion }{ available } - 1 ];
            push @{ $sections{ $section }{ allocated } }, @students[ @
+random ];
            $sections{ $section }{ available } = 0;
            @{ $chose } = grep{ 
                my $allocated = $_;
                !grep{ $_ == $allocated } @random
            } @$chose;
            push @allocated, @random;
#            print "Alloc3: \t\t\t[@{[ sort {$a<=>$b} @$chose ]}][@{[ 
+sort {$a<=>$b} @allocated ]}]";
        }
    }
    delete @students[ @allocated ];
    @students = grep{ defined } @students;
#    print "left: @students"; <STDIN>;
    last unless @students;
}

print "\nUnallocated after main pass; [@students]";

my @withPlaces = grep{ $sections{ $_ }{ available } } sort keys %secti
+ons;
print "Sections with places: [@withPlaces]\n";
@withPlaces = map{ m[(\d+)]; 0+$1 } @withPlaces;

my $sentinel = $students[ 0 ];
JIGGLE:
while( @students ## students without a place
    and sum( map{ $_->{ available } } values %sections ) ## and places
+ unallocated
) {
    my $unplaced = shift @students; ## Grab the first unplaced student
    
    for my $choice ( map{ sprintf 'Section_%03d', } @{ $students{ $unp
+laced } } ) { ## And look at their choices
        ## Look at the students currently allocated to each of those c
+hoices
        for my $placed ( @{ $sections{ $choice }{ allocated } } ) {
            print "looking at placed student $placed";            
            ## And check if there are places availble in any of their 
+alternate choices?
            my $alternateSection = first{  
                my $alt = $_;
                grep{ $alt == $_ } @withPlaces
            } @{ $students{ $placed } };
            
            ## If so,
            if( $alternateSection ) {
                $alternateSection = sprintf 'Section_%03d', $alternate
+Section;
                ## Remove them from their current placement, and add t
+he unplaced student in their place
                @{ $sections{ $choice }{ allocated } } = (
                    $unplaced,
                    grep{ !m[$placed] } @{ $sections{ $choice }{ alloc
+ated } }
                );
                
                ## And re-place them into that alternate
                push @{ $sections{ $alternateSection }{ allocated } },
+ $placed;

                ## And decrement the places available there.          
+      
                $sections{ $alternateSection }{ available }--;
                print "moved $placed to $alternateSection and put $unp
+laced in $choice\n";
                next JIGGLE;
            }
        }
        ## If we got here, then we couldn't jiggle a place for the las
+t unplaced student,
        ## so stick 'em back into the list. !!! POTENTIAL INFINITE LOO
+P !!!
        push @students, $unplaced;
        print "Failed to replace $unplaced\n";
        last JIGGLE if $students[ 0 ] = $sentinel; ## Crude, but this 
+loop has too many conditions!
    }
}

print "\nUnallocated after one-level jiggle(TM); [@students]";

print "$_($sections{ $_ }{ available }) => ", ref $sections{ $_ }{ all
+ocated }
    ? "[ @{ $sections{ $_ }{ allocated } } ]"
    : "[EMPTY]"
    for sort keys %sections;

[download]

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

Replies are listed 'Best First'.
Re^6: [OT] simple algorithm for assigning students to class sections
by hossman (Prior) on Dec 07, 2004 at 07:39 UTC
    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)

    Read more... (1126 Bytes)

    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;

    [download]

    (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

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom