(Football) Scheduling Algorithm

L

lomn75

Purple Ace
Joined
Jun 26, 2000
Messages
6,613
I'm playing around with a fantasy football system I came across on SourceForge trying to add a bunch of capabilities it lacks. Anyway, one of the nuisances is that the schedule has to be created in completely manual fashion. I figure there's got to be some way to automate this, but I'm having trouble putting it together.

Here's a basic situation: say there are 10 teams A through J, broken into two divisions A-E and F-J. Each team should play each other team in the division twice and each other team not in the division once. This works out to a 13 week season, and A's list of teams to play is B,B,C,C,D,D,E,E,F,G,H,I,J (the other teams have similar known lists). Anybody know how to then take these 10 lists and fashion a viable set of pairings out of them? I'd appreciate any input.
 
I'd rather work with numbers for some reason, ok so there's teams 1-5 and 6-10 in division A and B respectively.

Here's one way of doing it:
-Team 1 Schedule
Code: 
Loop 13 Times:
    Randomly select team from A
    Check if TeamX > 2 else put on 1's schedule, TeamX++ etc.  (also make sure TeamX != Team1)

    Randomly select team from B
    Check if TeamY > 1 else put on 1's schedule, TeamY++, etc.
Loop

It's rather wasteful because you would have to create variables for each team, but you could use an array to easily automate it all.

e.g. C/C++:

Code: 
x = randomlySelectedTeam

if(TeamList[x] < 2 && TeamList[x] != Team1)
{    TeamList[x] += 1;
     Put team on Team1's schedule...
}

Hope this helps, I know its crude, but its self governing in the fact that you don't have to change the list of teams every time. I'm sure once you get the basic algorithm down, you can perfect it from there.
 
Most teams have a bye week so be sure to account for that too. I would just make a nested loop with a two dimensional array to hold the team schedules.

So first schedule the divisional games. Rand and Rnd for VB and C are used for random numbers.

Then use a nested loop to check if every team is scheduled.
{code}

for i = min to max
'pre -determine all bye weeks -some random method
for w = minw to maxw
if sched{w,i} = 0 and byeweek = false then
'create random selection
end if
next w
next i

[/code]

It doesn't seem like it would be too bad. You could also replace the center for loop with a while.loop. Set a variable x = the number of weeks and decrement it as each team is scheduled. Set he condition of the while loop to exit when there is one week left.

Code: 
x = 13
'loop to determine x games remaining before here (13 to start with)

while x > 1
   week = 'random
   if sched[i, x] = 0 then
      opp = 'random 
      'schedule game for both teams
      x = x - 1
  end if
loop
  
[/code}

This may be confusing since I'm tired but ask if you don't get it. I don't think you'll have to worry about optomizing your code too much since its not like there are thousands of teams. So go for the algorithm that is easiest, unless you prefer to optomize it. There shouldn't be uch of a difference unless you are using thousands of teams, games, years, etc. For a single year and 30 teams or so it should be done in no time.
 
Perhaps I've misinterpreted your algo, but for a simpler example, here's the problem (as I see it) with a pure random approach.

This time I'll do teams 1-3 in Div A, 4-6 in Div B, same pattern for 7 games
Team 1, for instance, has a schedule in some order of 2,2,3,3,4,5,6
I've generated this order via die rolls.

Team 1 generates an order of 6,3,5,2,4,2,3

this backfills so that division A now looks like
Code: 
1: 6 3 5 2 4 2 3
2: - - - 1 - 1 -
3: - 1 - - - - 1
so far, so good.
Team 2 generates via die rolls 5,4,3,1,6,1,3. That last "3" is by default (as no other teams remain viable), but the problem already emerges that team 3 now has a conflict at game 7.
Code: 
1: 6 3 5 2 4 2 3
2: 5 4 3 1 6 1 3
3: - 1 2 - - - X
I figure this is really some sort of combinatorics / pigeonhole problem, but I can't get my head around it to save my life. Maybe some sort of availability array per game would be effective.
 
For the team conflict problem, couldn't you just check up the other team's schedules? Very easy to do if you took powerman's suggestion and made the schedules in a 2d array.
 
At least now you can see why it currently requires this to be calculated by hand. All I can really say about a solution is that :

"A proposed solution to the problem can trivially be verified in polynomial time..." ;)



TheDot : not really. This makes it easy to get each week consistant but does little to prevent you from making choices that would result in an unsolvable system (painting yourself into the metaphorical corner). You're either going to have to implement backtracking or find a way off solving the whole problem at once.

I'm thinking the best sol'n would be to randomly generate 1 week (maybe 2) and then find a way to mechanically derrive the rest of the schedule from there. Prolog seems like a first choice, but I'm sure you could come up with an equivalent recursive method of solving it. Find a direct solution would be tricky, to say the least.
 
For there to be no bye weeks, there must be at least 1 interdivision game each week and the the number of interdivision games per week must be odd.

Use of symmetry (if possible) could cut down on the work required. Week 7 would be the pivot point, so make it a fully interdivision week, else symmetry is not possible. At first, don't schedule a interdivision game between teams, schedule it from a team in one division to "the other division". If you can schedule 1 and only 1 match between each team in a division in the first 6 weeks, given 4 extra interdivision games over the 1 per week to schedule in those weeks (which must be scheduled either in a solid block or as a pair of 2s), then the problem is pretty much solved with only about a quarter of the work. Copy weeks 1 - 6 into weeks 8 - 13 (shuffle the row order if you wish) and then clone the schedule for the other division and do a one to one map of a team in the first division to a team in the second.

EDIT: Not quite so simple. Can't strictly copy 1 - 6 to 8 - 13, must shuffle the team assignments around (just rotate left or right for simplicity), else there will be duplicate interdivision games.
 
Possible first 6 weeks for Division I that is symmetric around a full, interdivision week 7 (x denotes an interdivision game).

1: Ax, Bx, Cx, Dx, Ex
2: Ax, BC, CB, DE, ED
3: AD, Bx, CE, DA, EC
4: AE, BD, Cx, DB, EA
5: AC, BE, CA, Dx, EB
6: AB, BA, CD, DC, Ex

Rotating team slots left (A goes to the position of E, B to A, etc.) and then copying for weeks 8 - 13 gives a Division 1 schedule of

1: Ax, Bx, Cx, Dx, Ex
2: Ax, BC, CB, DE, ED
3: AD, Bx, CE, DA, EC
4: AE, BD, Cx, DB, EA
5: AC, BE, CA, Dx, EB
6: AB, BA, CD, DC, Ex
7: Ax, Bx, Cx, Dx, Ex
8: Ex, Ax, Bx, Cx, Dx
9: Ex, AB, BA, CD, DC
10: EC, Ax, BD, CE, DB
11: ED, AC, Bx, CA, DE
12: EB, AD, BE, Cx, DA
13: EA, AE, BC, CB, Dx

Cloning weeks 1 - 7 and make 8 - 13 = 1 - 6 (to avoid rotating together, which defeats the purpose) and mapping A to F, etc. gives this

1: Ax, Bx, Cx, Dx, Ex | | Fx, Gx, Hx, Ix, Jx
2: Ax, BC, CB, DE, ED | | Fx, GH, HG, IJ, JI
3: AD, Bx, CE, DA, EC | | FI, Gx, HJ, IF, JH
4: AE, BD, Cx, DB, EA | | FJ, GI, Hx, IG, JF
5: AC, BE, CA, Dx, EB | | FH, GJ, HF, Ix, JG
6: AB, BA, CD, DC, Ex | | FG, GF, HI, IH, Jx
7: Ax, Bx, Cx, Dx, Ex | | Fx, Gx, Hx, Ix, Jx
8: Ex, Ax, Bx, Cx, Dx | | Fx, Gx, Hx, Ix, Jx
9: Ex, AB, BA, CD, DC | | Fx, GH, HG, IJ, JI
10: EC, Ax, BD, CE, DB | | FI, Gx, HJ, IF, JH
11: ED, AC, Bx, CA, DE | | FJ, GI, Hx, IG, JF
12: EB, AD, BE, Cx, DA | | FH, GJ, HF, Ix, JG
13: EA, AE, BC, CB, Dx | | FG, GF, HI, IH, Jx



Fill in the obvious to get this

1: Ax, Bx, Cx, Dx, Ex | | Fx, Gx, Hx, Ix, Jx
2: AF, BC, CB, DE, ED | | FA, GH, HG, IJ, JI
3: AD, BG, CE, DA, EC | | FI, GB, HJ, IF, JH
4: AE, BD, CH, DB, EA | | FJ, GI, HC, IG, JF
5: AC, BE, CA, DI, EB | | FH, GJ, HF, ID, JG
6: AB, BA, CD, DC, EJ | | FG, GF, HI, IH, JE
7: Ax, Bx, Cx, Dx, Ex | | Fx, Gx, Hx, Ix, Jx
8: Ex, Ax, Bx, Cx, Dx | | Fx, Gx, Hx, Ix, Jx
9: EF, AB, BA, CD, DC | | FE, GH, HG, IJ, JI
10: EC, AG, BD, CE, DB | | FI, GA, HJ, IF, JH
11: ED, AC, BH, CA, DE | | FJ, GI, HB, IG, JF
12: EB, AD, BE, CI, DA | | FH, GJ, HF, IC, JG
13: EA, AE, BC, CB, DJ | | FG, GF, HI, IH, JD


Assigning the remaining interdivision games one at a time, avoiding doubling up (no need to backtrack), gives this

1: AH, BI, CJ, DF, EG | | FD, GE, HA, IB, JC
2: AF, BC, CB, DE, ED | | FA, GH, HG, IJ, JI
3: AD, BG, CE, DA, EC | | FI, GB, HJ, IF, JH
4: AE, BD, CH, DB, EA | | FJ, GI, HC, IG, JF
5: AC, BE, CA, DI, EB | | FH, GJ, HF, ID, JG
6: AB, BA, CD, DC, EJ | | FG, GF, HI, IH, JE
7: AI, BJ, CF, DG, EH | | FC, GD, HE, IA, JB
8: EI, AJ, BF, CG, DH | | FB, GC, HD, IE, JA
9: EF, AB, BA, CD, DC | | FE, GH, HG, IJ, JI
10: EC, AG, BD, CE, DB | | FI, GA, HJ, IF, JH
11: ED, AC, BH, CA, DE | | FJ, GI, HB, IG, JF
12: EB, AD, BE, CI, DA | | FH, GJ, HF, IC, JG
13: EA, AE, BC, CB, DJ | | FG, GF, HI, IH, JD

Which is a full schedule that meets the specifications.

For variety, rows can be shuffled in any order, obviously. Also, swapping between letters in the same division for all weeks will also work: A becomes C and C becomes A, for example (watch out to use a temp character if using a text editor to do it via a replace function, else you'll end up with double the Cs and no As).

EDIT: While I show both orders of all team pairings in a given week (Example: AE, EA), it is just for ease of following things. It doesn't indicate that I believe that every game should be a double header.
 
Cleaning up the thought process, it can go like this:

1: Start with 6 weeks and one division.

2: Schedule 10 interdivision (don't bother assigning to a specific team in the other division) games such that the number of interdivision games in a given week is odd (meaning that there must be at least 1 per week) and each team is scheduled for 2 interdivision games.

3: Schedule the the remaining games as intradivision, such that each team plays every other team in its division once and only once.

4: Schedule week 7 as entirely interdivision.

5: Clone what you have and apply it to weeks 1 - 7 of the other division, mapping one to one a team from the 2nd Division to a team in the 1st Division.

6: Generate weeks 8 - 13 for the 1st Division by cloning weeks 1 - 6. EDIT: removed stuff that could possibly bork things (I'm not certain) and serves no purpose that isn't adressed elsewhere.

7: Clone weeks 8 - 13 (which, after the edit, are the same as weeks 1 - 6) from the 1st division to the 2nd, doing another mapping that does not intersect with the mapping used for weeks 1 - 7. (Example: If the mapping A -> F was used for weeks 1 - 7, it CAN'T be used for weeks 8 - 13.)

8: Fill in all obvious interdivision games (if there's 1 in a week, there's no doubt as to the teams involved).

9: Assign the remaining interdivision games such that there are no duplicates. (Easy to do. If there isn't a duplicate for the first pairing you try, make it. There won't be any need to undo any of the pairings you do.)

10 (optional): Move chunks of games between weeks, as long as all the teams in the games swapped are the same. Example: ...AD,BF... can trade places with ...AF,BD... in another week. (Obviously, ALL games in one week can be swapped with ALL games in another week, giving the effect of swapping the week numbers.) In this manner, schedule permutations could be generated that would be otherwise unavailable using only the prior steps.

Schedule is complete.

Step #3 is the most difficult, but it isn't all that hard, comparatively speaking. It certainly is much more efficient than trying to brute force a schedule.

With the inclusion of step #10, I believe it is possible to generate any possible schedule from this method. (I could probably do a proof, but I don't feel like it.)
 
Hmm... well, thanks for the input, guys. I'll probably shelve this one (at least for arbitrary arragements) for a while, though I should be able to hack in some common cases.
 
You must log in or register to reply here.
Back
Top