Date:         Fri, 28 Dec 2007 21:32:32 -0500
Reply-To:     "Howard Schreier <hs AT dc-sug DOT org>" <nospam@HOWLES.COM>
Sender:       "SAS(r) Discussion" <SAS-L@LISTSERV.UGA.EDU>
From:         "Howard Schreier <hs AT dc-sug DOT org>" <nospam@HOWLES.COM>
Subject:      Re: Randomly generating a season schedule for a (e.g.,
              soccer) league

On Mon, 24 Dec 2007 01:23:37 -0800, Daniel Nordlund <res90sx5@VERIZON.NET>
wrote:

>> -----Original Message-----
>> From: SAS(r) Discussion [mailto:SAS-L@LISTSERV.UGA.EDU] On Behalf Of Howard
>> Schreier <hs AT dc-sug DOT org>
>> Sent: Sunday, December 23, 2007 8:45 PM
>> To: SAS-L@LISTSERV.UGA.EDU
>> Subject: Re: Randomly generating a season schedule for a (e.g., soccer)
league
>>
>> On Sat, 22 Dec 2007 11:11:50 -0800, Oliver.Kuss@MEDIZIN.UNI-HALLE.DE wrote:
>>
>> >Hello all,
>> >I wonder if someone could help me with randomly generating a season
>> >schedule for a (e.g., soccer) league.
>> >Imagine you have 18 teams in your league, and every team should play
>> >each other team exactly once. This would result in 17 days to play,
>> >with 9 matches to play at each day. Of course, each team should only
>> >play one match each day.
>> >
>> >I tried to code such a season schedule with PROC PLAN, but did not
>> >succeed ...
>> >
>> >Maybe someone could point me to the right direction ...
>> >
>> >Thank you,
>> >Oliver
>>
>> I don't know PROC PLAN. Another possibility might be in SAS/OR. Otherwise I
>> think that a completely random schedule will be difficult. Is it really
>> necessary?
>>
>> Here is a DATA step which will generate an arbitrary schedule satisfying all
>> of the constraints.
>>

[Snip]

>>
>> When you assign actual team names to the team numbers and actual playing
>> dates to the day numbers, you can randomize those mappings. Won't that be
>> random enough?
>
>Howard,
>
>The code above has team 16 playing twice on day 1, and team 17 not playing
at all on day 1.  Actually, most days have one team playing twice and one
team not playing at all.
>
>Dan
>
>Daniel Nordlund
>Bothell, WA

Dan, thanks for checking that. I ran the code and looked at the output, just
not hard enough.

Here's my implementation of the cited algoritm (from the "Round Robin"
article in Wikipedia):

   %let nteams=18;

   data roundrobin;
   array mm ( %eval(&nteams + 1) ) _temporary_ ( 1:&nteams, . );
   do Day = 1 to &nteams - 1;
      do Game = 1 to &nteams / 2;
         Team =     min( mm(Game), mm(&nteams + 1 - Game) );
         Opponent = max( mm(Game), mm(&nteams + 1 - Game) );
         output;
         end;
      do team = 2 to &nteams + 1;
         mm( ifn( team=2, &nteams+1, team-1 ) ) = mm(team);
         end;
      end;
   run;

I persisted and came up with what is more or less an inverse (generating the
pairings first, then deriving game days). Here's what I have

   %let nteams=8;

   data roundrobin2(drop = sum);
   do Team = 1 to &nteams-1; do Opponent = team + 1 to &nteams;
      sum = team + opponent;
      sum = sum - ifn( sum > &nteams+3, &nteams-1, 0 );
      if team=1 then Day = &nteams + 1 - opponent;
      else select (sum - &nteams);
         when (1) day = 1;
         when (2) day = &nteams / 2;
         when (3) day = &nteams - 1;
         otherwise do;
            if mod(sum,2)=1 then day = (&nteams - sum   + 3) / 2;
            else                 day =  &nteams - sum/2 + 1     ;
            end;
         end;
      output;
      end; end;
   run;

This really needs explanation, which I cannot quite provide. It's basically
reverse engineering. I took an 8-team schedule produced by the first DATA
step above and displayed it in a triangle by running:

   proc tabulate data=roundrobin noseps formchar="            ";
   class team opponent;
   var day;
   table (mean n) * day * f=4.
         ,
         opponent
         ,
         team
         /
         rts=10 ;
   run;

The output:

                           Team

               1    2    3    4    5    6    7
   Opponent
   2           7    .    .    .    .    .    .
   3           6    3    .    .    .    .    .
   4           5    6    2    .    .    .    .
   5           4    2    5    1    .    .    .
   6           3    5    1    4    7    .    .
   7           2    1    4    7    3    6    .
   8           1    4    7    3    6    2    5

Then I looked at patterns. The first column has its own distinct pattern,
which I noted. Then I looked at the triangle *excluding* the first column.
The diagonals running from lower left to upper right are constant. The
sequence in column 2 excluding the last 2 numbers repeats in the bottom row,
beginning in column 4 (always column 4, regardless of the number of teams).
Anyway, the code I cooked up essentially reflects these patterns.