note
BrowserUk
<blockquote><i>Thoughts?</i></blockquote>
<p>Yes. You need a Jiggle® :)
<ol><li>For each unallocated student's choices
</li><li>For each student currently allocated to that choice.
</li><li>For each of their alternate choices
</li><li>If that alternate has spaces
</li><li>Swap the unallocated student with the allocated student, and assign the previously placed student into the section with places available.
</li><li>Repeat until everyone is allocated; or you gave it your best shot.
</li></ol>
<p>Of course, that doesn't guarentee a solution, but it seems to do remarkably well if a solution is possible.
<p>I couldn't reproduce your exact example (without hard coding it) but I found a couple of similar one that the above Jiggle solves:
<code>
[ 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 ]
</code>
<p>And one which it didn't, but I don't thinkhas a solution with a one-level Jiggle?:
<code>
[ 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 ]
</code>
<p>It also seems to work pretty well on much larger tasks (Output substantially trimmed to show just those affected by the jiggle:
<readmore><code>
[ 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 Student_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>
</code></readmore>
<p>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).
<p>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.
<p>The main body of the code is unchanged except I made the generator a little less prone to producing insoluble datasets.
<p>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?
<readmore><code>
#! 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) <=> ($students{ $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 }{ available } ) {
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{ $section }{ 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 %sections;
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{ $unplaced } } ) { ## And look at their choices
## Look at the students currently allocated to each of those choices
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', $alternateSection;
## Remove them from their current placement, and add the unplaced student in their place
@{ $sections{ $choice }{ allocated } } = (
$unplaced,
grep{ !m[$placed] } @{ $sections{ $choice }{ allocated } }
);
## 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 $unplaced in $choice\n";
next JIGGLE;
}
}
## If we got here, then we couldn't jiggle a place for the last unplaced student,
## so stick 'em back into the list. !!! POTENTIAL INFINITE LOOP !!!
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{ $_ }{ allocated }
? "[ @{ $sections{ $_ }{ allocated } } ]"
: "[EMPTY]"
for sort keys %sections;
</code></readmore>
<p>PS. Sorry for leaving PM to do the wrapping -- it's been a long night :)
<div class="pmsig"><div class="pmsig-171588">
<hr />
<font size=1 >
<div>Examine what is said, not who speaks.</div>
"But you should never overestimate the ingenuity of the sceptics to come up with a counter-argument." -Myles Allen<br />
"Think for yourself!" - [Abigail-II|Abigail]
"Time is a poor substitute for thought"--[theorbtwo]
"Efficiency is intelligent laziness." -David Dunham
<br />
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - [tachyon]<br />
</font>
</div></div>
411129
412449