Sorting algorithm to keep doubleheaders back-to-back-CodePudding

In the context of sports scheduling I have a list of games where teams play more than 1x game, potentially. If that's the case, their games should be back-to-back. Since this is possibly not feasable due to the very nature of pairings, at least they should be as close together as possible.

This is an example of initial pairings where each team plays 2x:

[('t05', 't09'), ('t07', 't03'), ('t01', 't09'), ('t03', 't01'), ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't08'), ('t10', 't04'), ('t08', 't02')]

Note that this is not a double round-robin configuration where every team plays every other twice in a home and away game. This is simply a configuration where teams play two games.

I am trying to implement an algorithm to sort these games to keep every team's games as close together as possible. This is the first, simple approach:

matches = list(matches)
c = collections.Counter([t for m in matches for t in m.teams])
for t, n in c.iteritems():
    if n > 1:
        # matches containing the team t
        indices = [i for i, m in enumerate(matches) if t in m.teams]
        for i in indices:
            # bring these matches to the front
            matches.insert(0, matches.pop(i))
return matches

This is the result:

[('t10', 't04'), ('t10', 't08'), ('t01', 't09'), ('t05', 't09'), ('t08', 't02'), ('t07', 't03'), ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t03', 't01')]

Obviously it's not very good, as it's one sided and it benefits more the teams at the end of the list by placing their games at the front of the list. With one-sided I mean it looks at just one team in each game and works the sorting for that team, disregarding the second team, which will break the back-to-back balance for that other team.

This would be a perfect case of a maximization using constraint programming, for example using python-constraint or pyomo. But I am really bad at modelling constraint satisfaction problems (CSP) so I wouldn't have a clue of where to start with this case.

Any ideas?

CodePudding user response：

A recursive function can try various orderings in a dynamic programming fashion that prioritizes connected games over breaks in the sequence.

This one is not particularly optimized but should work quick enough for small lists of games:

def gameOrder(games,prevGame=None):
    if len(games)==1: return games    # base condition (only one game)
    best,breaks = games,len(games)-1  # track best order and number of breaks
    for strict in (1,0):              # prioritize connections over breaks
        for i,game in enumerate(games): # each game as 1st in sequence
            if breaks <= strict: return best  # minimum breaks reached
            if strict and prevGame and prevGame.isdisjoint(game): 
                continue # does not connect to previous (strict)
            seq = [game] gameOrder(games[:i] games[i 1:],set(game)) # sort rest
            brk = sum(set(g1).isdisjoint(g2) for g1,g2 in zip(seq,seq[1:]))
            if brk < breaks:
                breaks,best = brk,seq # track best so far
    return best # return best found

Output:

games = [('t05', 't09'), ('t07', 't03'), ('t01', 't09'), ('t03', 't01'), 
         ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't08'), 
         ('t10', 't04'), ('t08', 't02')]

print(gameOrder(games)) # only one break between (t07,t05) and (t02,t06)
[('t05', 't09'), ('t01', 't09'), ('t03', 't01'), ('t07', 't03'), 
 ('t07', 't05'), ('t02', 't06'), ('t04', 't06'), ('t10', 't04'), 
 ('t10', 't08'), ('t08', 't02')]

Note that this ensures that as many teams as possible have consecutive games. It may not be the best solution if your goal is to minimize the worst case 'distance' between games for any teams, or minimize the average game distance per team.