package Schedule::RoundRobin; ############################################################################### # implements a round robin scheduling algorithm as described in # http://forum.swarthmore.edu/dr.math/problems/kinley.3.31.00.html ############################################################################### # takes an array and returns a reference to a list of pairs sub schedule { my(@teams) = @_; # get the size of the array my \$size = scalar @teams; # If it is even, pop off one item and maintain it as a central point # and proceed as with an odd number return undef unless (\$size > 0); my \$pivot = undef; my \$even = 0; my \$end_point_a = 0; my \$end_point_b = \$size-1; if(\$size%2 == 0) { # \$pivot = pop @teams; \$pivot = \$#teams; \$even = 1; \$end_point_b--; } # Create a list of the "stripes" of the polygon, the stripes will be # pairs of indices into the array my @stripes; # Assume that each element in the array is a vertex of the polygon # and the vertices are listed in order, stripes are created for (1..int((\$size-1)/2)) { push(@stripes, [\$end_point_a, \$end_point_b]); \$end_point_a++; \$end_point_b--; } # Upon falling out of the loop, the middle point will be in both # end_point_a and end_point_b if(\$even) { push(@stripes, [\$end_point_a, \$pivot]); } # Each element of the games array is a play date's worth of games # so it is an array of pairs my @games; for(1..(\$size-\$even)) { my @this_week; # push the weeks worth of games onto @games foreach my \$sched_ref (@stripes) { push (@this_week, [\$teams[\$sched_ref->[0]], \$teams[\$sched_ref->[1]]]); } push(@games, \@this_week); # Now rotate the @teams array my \$last_team_save = undef; # Save the last team as the pivot for the polygon if(\$even) { \$last_team_save = pop(@teams); } my \$last_team = pop(@teams); unshift(@teams, \$last_team); if(\$even) { push(@teams, \$last_team_save); } } return \@games; } 1;