So I have a program that creates a schedule for every single NFL team and all of the lists are in a dictionary. The point is that I will have lists with 16 teams and I want to have one team play another team every single week, so it would look something like this for week 1 (As a sorted list not the original list which contains all 16 teams they will play).
'Washington': ['Cowboys'],
'Cowboys': ['Washington'],
'Eagles': ['Giants'],
'Giants': ['Eagles'],
This has to work with all 32 teams and for every week. I'm not interested in bi-weeks or the 17-game schedule, just trying to make the created schedule be organized so that every team can play another team that is still in their schedule and that they haven't already played in their schedule.
Here's an example for just 1, where it shows every team they will play but it isn't organized in an order way. Also this is only 1 list of teams to play, not the full 32 teams. (Stack overflow thinks posting more schedules of repeating team names is spam)
Washington ['Eagles', 'Giants', 'Cowboys', 'Eagles', 'Giants', 'Cowboys', 'Vikings', 'Packers', 'Bears', 'Lions', 'Chargers', 'Chiefs', 'Raiders', 'Broncos', 'Buccaneers', 'Rams']
I'm first asking if there's even a way to sort all of these lists to find the right order to make a new list with the teams in order, and if there is, how can I do this?
CodePudding user response：
[proposed round-robin solution removed as it was not applicable]
The problem can be converted to a graph where each distinct game is a vertex and the edges are links to other games that don't conflict (i.e. other games that don't involve the same teams). Each week's schedule will be a maximum clique in that graph and there will be 16 disjoint cliques of 16 games in the 256 node graph.
Finding maximum cliques is a well known NP-Complete problem but given the constraints, there may be a dynamic programming solution. Having 16 disjoint cliques of 16 games means that the full graph is covered by these cliques so every game will go in exactly one of these cliques. We can also leverage the fact that we know of 16 games that each belong to a different clique and can serve as anchors to expand the 16 distinct cliques (e.g. the 16 matches with the 49ers for example).
My initial attempts at solving this with DP were unsuccessful and would take forever to converge to an answer. They worked on a small schedule generated with the round-robin algorithm but failed with the 32 teams dictionary.
[EDIT] Found a solution that may work
After realizing that there were repeated teams in the lists I figured out why my initial graph solutions were failing. This gave me an idea for one final attempt that actually worked (at least for the data sample you provided in a comment and for shuffled round-robin schedules I tested).
The solution is an optimized variant of the graph algorithm I was playing with. The graph's vertices are now unique games (team pairs) that allow for repetitions. The algorithm uses a list of game sets (one per week) and attempts to place each game (vertex) in one of the weeks while respecting constraints. It backtracks the game placements when it hits a dead end. Combined with a dynamic prioritization of games to place, the program reverse engineers the schedule within seconds (it was still taking an inordinate amount of time without the prioritization).
Note that, although it did in all my tests, I cannot be sure that the program will always respond as rapidly with different data. That's why I'm only saying this MAY work.
Input
matches = {
'Washington': ['Eagles', 'Cowboys', 'Giants', 'Eagles', 'Cowboys', 'Giants', 'Rams', 'Cardinals', 'Seahawks', '49ers', 'Dolphins', 'Jets', 'Patriots', 'Bills', 'Bears', 'Panthers'],
'Cowboys': ['Eagles', 'Washington', 'Giants', 'Eagles', 'Washington', 'Giants', 'Rams', 'Cardinals', 'Seahawks', '49ers', 'Dolphins', 'Jets', 'Patriots', 'Bills', 'Packers', 'Falcons'],
'Eagles': ['Washington', 'Cowboys', 'Giants', 'Washington', 'Cowboys', 'Giants', 'Rams', 'Cardinals', 'Seahawks', '49ers', 'Dolphins', 'Jets', 'Patriots', 'Bills', 'Lions', 'Buccaneers'],
'Giants': ['Eagles', 'Washington', 'Cowboys', 'Eagles', 'Washington', 'Cowboys', 'Rams', 'Cardinals', 'Seahawks', '49ers', 'Dolphins', 'Jets', 'Patriots', 'Bills', 'Vikings', 'Saints'],
'Seahawks': ['Rams', 'Cardinals', '49ers', 'Rams', 'Cardinals', '49ers', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Falcons', 'Packers'],
'Cardinals': ['Rams', 'Seahawks', '49ers', 'Rams', 'Seahawks', '49ers', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Panthers', 'Bears'],
'Rams': ['Cardinals', 'Seahawks', '49ers', 'Cardinals', 'Seahawks', '49ers', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Buccaneers', 'Lions'],
'49ers': ['Rams', 'Cardinals', 'Seahawks', 'Rams', 'Cardinals', 'Seahawks', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Saints', 'Vikings'],
'Packers': ['Lions', 'Bears', 'Vikings', 'Lions', 'Bears', 'Vikings', 'Buccaneers', 'Panthers', 'Falcons', 'Saints', 'Raiders', 'Broncos', 'Chiefs', 'Chargers', 'Cowboys', 'Seahawks'],
'Lions': ['Bears', 'Packers', 'Vikings', 'Bears', 'Packers', 'Vikings', 'Buccaneers', 'Panthers', 'Falcons', 'Saints', 'Raiders', 'Broncos', 'Chiefs', 'Chargers', 'Eagles', 'Rams'],
'Bears': ['Lions', 'Packers', 'Vikings', 'Lions', 'Packers', 'Vikings', 'Buccaneers', 'Panthers', 'Falcons', 'Saints', 'Raiders', 'Broncos', 'Chiefs', 'Chargers', 'Washington', 'Cardinals'],
'Vikings': ['Lions', 'Bears', 'Packers', 'Lions', 'Bears', 'Packers', 'Buccaneers', 'Panthers', 'Falcons', 'Saints', 'Raiders', 'Broncos', 'Chiefs', 'Chargers', 'Giants', '49ers'],
'Buccaneers': ['Panthers', 'Falcons', 'Saints', 'Panthers', 'Falcons', 'Saints', 'Lions', 'Bears', 'Packers', 'Vikings', 'Titans', 'Colts', 'Jaguars', 'Texans', 'Rams', 'Eagles'],
'Falcons': ['Buccaneers', 'Panthers', 'Saints', 'Buccaneers', 'Panthers', 'Saints', 'Lions', 'Bears', 'Packers', 'Vikings', 'Titans', 'Colts', 'Jaguars', 'Texans', 'Seahawks', 'Cowboys'],
'Panthers': ['Buccaneers', 'Falcons', 'Saints', 'Buccaneers', 'Falcons', 'Saints', 'Lions', 'Bears', 'Packers', 'Vikings', 'Titans', 'Colts', 'Jaguars', 'Texans', 'Cardinals', 'Washington'],
'Saints': ['Buccaneers', 'Panthers', 'Falcons', 'Buccaneers', 'Panthers', 'Falcons', 'Lions', 'Bears', 'Packers', 'Vikings', 'Titans', 'Colts', 'Jaguars', 'Texans', '49ers', 'Giants'],
'Patriots': ['Dolphins', 'Jets', 'Bills', 'Dolphins', 'Jets', 'Bills', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Chiefs', 'Jaguars'],
'Bills': ['Dolphins', 'Jets', 'Patriots', 'Dolphins', 'Jets', 'Patriots', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Chargers', 'Texans'],
'Dolphins': ['Jets', 'Patriots', 'Bills', 'Jets', 'Patriots', 'Bills', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Raiders', 'Titans'],
'Jets': ['Dolphins', 'Patriots', 'Bills', 'Dolphins', 'Patriots', 'Bills', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Broncos', 'Colts'],
'Chargers': ['Raiders', 'Broncos', 'Chiefs', 'Raiders', 'Broncos', 'Chiefs', 'Titans', 'Colts', 'Jaguars', 'Texans', 'Lions', 'Bears', 'Packers', 'Vikings', 'Bills', 'Steelers'],
'Raiders': ['Broncos', 'Chiefs', 'Chargers', 'Broncos', 'Chiefs', 'Chargers', 'Titans', 'Colts', 'Jaguars', 'Texans', 'Lions', 'Bears', 'Packers', 'Vikings', 'Dolphins', 'Bengals'],
'Chiefs': ['Raiders', 'Broncos', 'Chargers', 'Raiders', 'Broncos', 'Chargers', 'Titans', 'Colts', 'Jaguars', 'Texans', 'Lions', 'Bears', 'Packers', 'Vikings', 'Patriots', 'Browns'],
'Broncos': ['Raiders', 'Chiefs', 'Chargers', 'Raiders', 'Chiefs', 'Chargers', 'Titans', 'Colts', 'Jaguars', 'Texans', 'Lions', 'Bears', 'Packers', 'Vikings', 'Jets', 'Ravens'],
'Ravens': ['Bengals', 'Browns', 'Steelers', 'Bengals', 'Browns', 'Steelers', 'Dolphins', 'Jets', 'Patriots', 'Bills', 'Rams', 'Cardinals', 'Seahawks', '49ers', 'Colts', 'Broncos'],
'Browns': ['Bengals', 'Ravens', 'Steelers', 'Bengals', 'Ravens', 'Steelers', 'Dolphins', 'Jets', 'Patriots', 'Bills', 'Rams', 'Cardinals', 'Seahawks', '49ers', 'Jaguars', 'Chiefs'],
'Bengals': ['Ravens', 'Browns', 'Steelers', 'Ravens', 'Browns', 'Steelers', 'Dolphins', 'Jets', 'Patriots', 'Bills', 'Rams', 'Cardinals', 'Seahawks', '49ers', 'Titans', 'Raiders'],
'Steelers': ['Bengals', 'Ravens', 'Browns', 'Bengals', 'Ravens', 'Browns', 'Dolphins', 'Jets', 'Patriots', 'Bills', 'Rams', 'Cardinals', 'Seahawks', '49ers', 'Texans', 'Chargers'],
'Colts': ['Titans', 'Jaguars', 'Texans', 'Titans', 'Jaguars', 'Texans', 'Raiders', 'Broncos', 'Chiefs', 'Chargers', 'Buccaneers', 'Panthers', 'Falcons', 'Saints', 'Ravens', 'Jets'],
'Jaguars': ['Titans', 'Colts', 'Texans', 'Titans', 'Colts', 'Texans', 'Raiders', 'Broncos', 'Chiefs', 'Chargers', 'Buccaneers', 'Panthers', 'Falcons', 'Saints', 'Browns', 'Patriots'],
'Texans': ['Titans', 'Colts', 'Jaguars', 'Titans', 'Colts', 'Jaguars', 'Raiders', 'Broncos', 'Chiefs', 'Chargers', 'Buccaneers', 'Panthers', 'Falcons', 'Saints', 'Steelers', 'Bills'],
'Titans': ['Colts', 'Jaguars', 'Texans', 'Colts', 'Jaguars', 'Texans', 'Raiders', 'Broncos', 'Chiefs', 'Chargers', 'Buccaneers', 'Panthers', 'Falcons', 'Saints', 'Bengals', 'Dolphins']}
Data structures:
gamesis the list of distinct games. Because teams can be paired more than once, I'm using indexes in that list of games as my vertex identifiers so that repeated pairings can be processed as separate game instances. The list is used at the end to convert the schedule back into team pairs.graphis a dictionary with one entry per game ID and a set of compatible games that can be played the same weekweeksis a list of sets in which the algorithm will "pigeonhole" the games while respecting constraints of compatibility and completeness (ending up with 16 games each week)weekMaxis also a list of sets but it contains the game IDs that are scheduled or that can be scheduled for each week. These sets are updated every time a game is scheduled and will contain fewer "potential" games as the scheduled games limit the possible other games. These sets are also used to detect "impossible week fill" situations early (i.e. not enough potential games remaining to fill the week)gameWeekskeeps track of the week number assigned to scheduled games. This is used to manage the progression through all possible permutations and to handle backtracking.weeks,weekMaxandgameWeeksstart out with the first 16 games (from '49ers') because those don't have any dependencies and can be fixed.
...
nbWeeks = len(matches[min(matches)]) # number of weeks (16)
GPW = len(matches)//2 # games per week (16)
nbGames = nbWeeks*GPW # total numebr of games
games = [(t,o) for t,opps in sorted(matches.items()) for o in opps if t<o ]
graph = dict()
for i,g in enumerate(games): # build graph { gameID:{compatible game IDs} }
graph[i] = {j for j,(t,o) in enumerate(games) if not (t in g or o in g) }
weeks = [{i} for i in range(nbWeeks)] # scheduled games for each week
weekMax = [graph[i]|{i} for i in range(nbWeeks)] # possible games that week
gameWeeks = [-1]*len(games) # week of each game (-1 = not scheduled yet)
gameWeeks[:nbWeeks]=range(nbWeeks) # weeks of base games (those are fixed)
Solution seeker, with backtracking
priority = [*range(len(games))] # games IDs in priority order
gi = nbWeeks # current game index to schedule
while gi>=nbWeeks and gi<nbGames: # loop to schedule every game
g = priority[gi]
if gameWeeks[g] == -1: # prioritize game after moving forward
pi,g = min(enumerate(priority[gi:],gi),
key=lambda ip:sum(ip[1] in wm for wm in weekMax))
priority.insert(gi,priority.pop(pi))
remaining = set(priority[gi 1:]) # game IDs remainnig to schedule
w = gameWeeks[g] # current week of game to schedule
if w >= 0:
weeks[w].discard(g) # remove game from its current week
gameWeeks[g] = -1
weekMax[w] = graph[w].intersection(*(graph[s] for s in weeks[w]))
weekMax[w] |= weeks[w]
w = 1 # find new week to schedule game
while w<nbWeeks and ( len(weeks[w])==GPW \
or g not in weekMax[w] \
or not graph[g].issuperset(weeks[w]) \
or len(graph[g] & weekMax[w] & (weeks[w] | remaining)) < GPW-1 ):
w = 1
if w==nbWeeks: # can't place game in any week
gi -= 1 # backtrack
remaining = set(priority[gi 1:])
continue
weeks[w].add(g) # Assign game to week
gameWeeks[g] = w # and week to game
weekMax[w] &= graph[g] # update possible games that week
weekMax[w].add(g) # including the one just scheduled
if any(len(wg) len(wm & remaining)<GPW for wg,wm in zip(weeks,weekMax)):
continue # caused impossible week fill, move on to other week
gi = 1 # game scheduled, move on to next game
Building the result from the week schedules
result = { t:[] for t in matches }
for schedule in weeks:
for g in schedule:
t,o = games[g]
result[t].append(o)
result[o].append(t)
for team,opponents in result.items():
print(team,opponents)
...
Washington ['Cardinals', 'Dolphins', 'Patriots', 'Bills', 'Bears', 'Giants', 'Panthers', '49ers', 'Seahawks', 'Eagles', 'Eagles', 'Cowboys', 'Giants', 'Cowboys', 'Jets', 'Rams']
Cowboys ['Patriots', 'Eagles', 'Dolphins', 'Seahawks', 'Giants', 'Eagles', 'Rams', 'Cardinals', '49ers', 'Bills', 'Jets', 'Washington', 'Packers', 'Washington', 'Giants', 'Falcons']
Eagles ['Giants', 'Cowboys', 'Giants', 'Patriots', 'Seahawks', 'Cowboys', '49ers', 'Jets', 'Dolphins', 'Washington', 'Washington', 'Rams', 'Cardinals', 'Buccaneers', 'Bills', 'Lions']
Giants ['Eagles', 'Vikings', 'Eagles', 'Dolphins', 'Cowboys', 'Washington', 'Seahawks', 'Rams', 'Jets', '49ers', 'Saints', 'Bills', 'Washington', 'Cardinals', 'Cowboys', 'Patriots']
Seahawks ['Bengals', 'Browns', '49ers', 'Cowboys', 'Eagles', '49ers', 'Giants', 'Ravens', 'Washington', 'Cardinals', 'Steelers', 'Cardinals', 'Falcons', 'Rams', 'Rams', 'Packers']
Cardinals ['Washington', '49ers', 'Rams', 'Steelers', '49ers', 'Rams', 'Bengals', 'Cowboys', 'Browns', 'Seahawks', 'Bears', 'Seahawks', 'Eagles', 'Giants', 'Ravens', 'Panthers']
Rams ['49ers', 'Bengals', 'Cardinals', '49ers', 'Browns', 'Cardinals', 'Cowboys', 'Giants', 'Ravens', 'Steelers', 'Buccaneers', 'Eagles', 'Lions', 'Seahawks', 'Seahawks', 'Washington']
49ers ['Rams', 'Cardinals', 'Seahawks', 'Rams', 'Cardinals', 'Seahawks', 'Eagles', 'Washington', 'Cowboys', 'Giants', 'Bengals', 'Ravens', 'Browns', 'Steelers', 'Saints', 'Vikings']
Packers ['Vikings', 'Bears', 'Vikings', 'Bears', 'Chiefs', 'Chargers', 'Saints', 'Broncos', 'Raiders', 'Buccaneers', 'Panthers', 'Lions', 'Cowboys', 'Lions', 'Falcons', 'Seahawks']
Lions ['Bears', 'Buccaneers', 'Bears', 'Broncos', 'Chargers', 'Vikings', 'Vikings', 'Saints', 'Chiefs', 'Raiders', 'Falcons', 'Packers', 'Rams', 'Packers', 'Panthers', 'Eagles']
Bears ['Lions', 'Packers', 'Lions', 'Packers', 'Washington', 'Panthers', 'Falcons', 'Chargers', 'Vikings', 'Vikings', 'Cardinals', 'Buccaneers', 'Saints', 'Raiders', 'Chiefs', 'Broncos']
Vikings ['Packers', 'Giants', 'Packers', 'Saints', 'Buccaneers', 'Lions', 'Lions', 'Chiefs', 'Bears', 'Bears', 'Chargers', 'Falcons', 'Panthers', 'Broncos', 'Raiders', '49ers']
Buccaneers ['Panthers', 'Lions', 'Saints', 'Panthers', 'Vikings', 'Falcons', 'Titans', 'Falcons', 'Saints', 'Packers', 'Rams', 'Bears', 'Texans', 'Eagles', 'Colts', 'Jaguars']
Falcons ['Saints', 'Saints', 'Panthers', 'Colts', 'Panthers', 'Buccaneers', 'Bears', 'Buccaneers', 'Titans', 'Texans', 'Lions', 'Vikings', 'Seahawks', 'Jaguars', 'Packers', 'Cowboys']
Panthers ['Buccaneers', 'Colts', 'Falcons', 'Buccaneers', 'Falcons', 'Bears', 'Washington', 'Texans', 'Jaguars', 'Saints', 'Packers', 'Saints', 'Vikings', 'Titans', 'Lions', 'Cardinals']
Saints ['Falcons', 'Falcons', 'Buccaneers', 'Vikings', 'Jaguars', 'Titans', 'Packers', 'Lions', 'Buccaneers', 'Panthers', 'Giants', 'Panthers', 'Bears', 'Texans', '49ers', 'Colts']
Patriots ['Cowboys', 'Chiefs', 'Washington', 'Eagles', 'Jets', 'Jets', 'Ravens', 'Bills', 'Bills', 'Jaguars', 'Dolphins', 'Steelers', 'Bengals', 'Browns', 'Dolphins', 'Giants']
Bills ['Dolphins', 'Jets', 'Jets', 'Washington', 'Ravens', 'Dolphins', 'Texans', 'Patriots', 'Patriots', 'Cowboys', 'Browns', 'Giants', 'Steelers', 'Bengals', 'Eagles', 'Chargers']
Dolphins ['Bills', 'Washington', 'Cowboys', 'Giants', 'Raiders', 'Bills', 'Jets', 'Steelers', 'Eagles', 'Bengals', 'Patriots', 'Browns', 'Jets', 'Ravens', 'Patriots', 'Titans']
Jets ['Steelers', 'Bills', 'Bills', 'Browns', 'Patriots', 'Patriots', 'Dolphins', 'Eagles', 'Giants', 'Broncos', 'Cowboys', 'Bengals', 'Dolphins', 'Colts', 'Washington', 'Ravens']
Chargers ['Raiders', 'Raiders', 'Jaguars', 'Texans', 'Lions', 'Packers', 'Colts', 'Bears', 'Broncos', 'Titans', 'Vikings', 'Chiefs', 'Broncos', 'Chiefs', 'Steelers', 'Bills']
Raiders ['Chargers', 'Chargers', 'Texans', 'Chiefs', 'Dolphins', 'Broncos', 'Broncos', 'Colts', 'Packers', 'Lions', 'Chiefs', 'Titans', 'Jaguars', 'Bears', 'Vikings', 'Bengals']
Chiefs ['Broncos', 'Patriots', 'Broncos', 'Raiders', 'Packers', 'Texans', 'Jaguars', 'Vikings', 'Lions', 'Colts', 'Raiders', 'Chargers', 'Titans', 'Chargers', 'Bears', 'Browns']
Broncos ['Chiefs', 'Titans', 'Chiefs', 'Lions', 'Colts', 'Raiders', 'Raiders', 'Packers', 'Chargers', 'Jets', 'Ravens', 'Jaguars', 'Chargers', 'Vikings', 'Texans', 'Bears']
Ravens ['Browns', 'Steelers', 'Bengals', 'Bengals', 'Bills', 'Steelers', 'Patriots', 'Seahawks', 'Rams', 'Browns', 'Broncos', '49ers', 'Colts', 'Dolphins', 'Cardinals', 'Jets']
Browns ['Ravens', 'Seahawks', 'Steelers', 'Jets', 'Rams', 'Bengals', 'Steelers', 'Bengals', 'Cardinals', 'Ravens', 'Bills', 'Dolphins', '49ers', 'Patriots', 'Jaguars', 'Chiefs']
Bengals ['Seahawks', 'Rams', 'Ravens', 'Ravens', 'Steelers', 'Browns', 'Cardinals', 'Browns', 'Steelers', 'Dolphins', '49ers', 'Jets', 'Patriots', 'Bills', 'Titans', 'Raiders']
Steelers ['Jets', 'Ravens', 'Browns', 'Cardinals', 'Bengals', 'Ravens', 'Browns', 'Dolphins', 'Bengals', 'Rams', 'Seahawks', 'Patriots', 'Bills', '49ers', 'Chargers', 'Texans']
Colts ['Titans', 'Panthers', 'Titans', 'Falcons', 'Broncos', 'Jaguars', 'Chargers', 'Raiders', 'Texans', 'Chiefs', 'Jaguars', 'Texans', 'Ravens', 'Jets', 'Buccaneers', 'Saints']
Jaguars ['Texans', 'Texans', 'Chargers', 'Titans', 'Saints', 'Colts', 'Chiefs', 'Titans', 'Panthers', 'Patriots', 'Colts', 'Broncos', 'Raiders', 'Falcons', 'Browns', 'Buccaneers']
Texans ['Jaguars', 'Jaguars', 'Raiders', 'Chargers', 'Titans', 'Chiefs', 'Bills', 'Panthers', 'Colts', 'Falcons', 'Titans', 'Colts', 'Buccaneers', 'Saints', 'Broncos', 'Steelers']
Titans ['Colts', 'Broncos', 'Colts', 'Jaguars', 'Texans', 'Saints', 'Buccaneers', 'Jaguars', 'Falcons', 'Chargers', 'Texans', 'Raiders', 'Chiefs', 'Panthers', 'Bengals', 'Dolphins']
Note that this is only one of many solutions. With just this one, you could generate 20,922,789,887,999 others merely from permutations of the weeks
VALIDATION
# Each week must have 32 distinct teams playing
for teams in zip(*result.values()):
if len(set(teams))!=32: print("error",teams)
# Each team must have the same list of opponents as originally
for (team,opponents),scheduled in zip(matches.items(),result.values()):
if sorted(opponents) != sorted(scheduled):
print("scheduling error",team)
print(" matches:",sorted(opponents))
print(" scheduled:",sorted(scheduled))
# No errors are printed