Generating natural schedule for a sports league

问题:

I'm looking for an algorithm to generate a schedule for a set of teams. For example, imagine a sports season in which each team plays each other, one time as home team and the other as a visitor team on another teams field.

To generate a set of all games in the season is easy, if teams is a list of teams the following would do:

set((x, y) for x in teams for y in teams if x != y)

But I also want to ORDER the games in chronological order in such a way that it satisfies the constraint of a valid game schedule and also looks "naturally random".

The constraint is that the game list should be groupable into a number of rounds where each round consists of n / 2 games (where n is the number of teams) in which each team is paired with another one.

To make the schedule look more natural, two teams should not face each other twice in consecutive rounds. That is, if (a, b) is played in one round, the game (b, a) should not be played in the ext one.

Also, as much as possible every team should play every other round as the away team and the other rounds as the home team. I don't think it is possible to always fulfill this constraint, so it is more a nice to have thing. For instance, one team shouldn't play 8 home games and then 8 away games.

Below is what I got now. The main problem with the algorithm is that it gets stuck in the while-loop quite often. Especially when the number of teams is 16 or more. It also is very inefficient because it builds on using the random sample function and hoping to get it right:

from random import sample
def season_schedule_order(teams, pairs):
    n_games_per_round = len(teams) // 2
    last_pairs = set()
    while pairs:
        r_pairs = set(sample(pairs, n_games_per_round))
        # Check that each team is present once in the round.
        r_teams = set(x for (x, y) in r_pairs) | set(y for (x, y) in r_pairs)
        if r_teams != teams:
            continue
        # Check that two teams doesn't face each other again.
        rev_pairs = set((y, x) for (x, y) in r_pairs)
        if rev_pairs & last_pairs:
            continue
        pairs -= r_pairs
        for p in r_pairs:
            yield p
        last_pairs = r_pairs

teams = set(['aik', 'djurgarden', 'elfsborg', 'gais',
             'gefle', 'hacken', 'halmstad', 'helsingborg'])
pairs = set((x, y) for x in teams for y in teams if x != y)
for (ht, at) in season_schedule_order(teams, pairs):
    print '%-20s %-20s' % (ht, at)

回答1:

I found a method here which I adapted slightly to this:

def round_robin(units, sets = None):
    """ Generates a schedule of "fair" pairings from a list of units """
    count = len(units)
    sets = sets or (count - 1)
    half = count / 2
    for turn in range(sets):
        left = units[:half]
        right = units[count - half - 1 + 1:][::-1]
        pairings = zip(left, right)
        if turn % 2 == 1:
            pairings = [(y, x) for (x, y) in pairings]
        units.insert(1, units.pop())
        yield pairings

teams = ['a', 'b', 'c', 'd']
print list(round_robin(teams, sets = len(teams) * 2 - 2))

Now I just need to turn this into plpgsql. :)

回答2:

REQUIREMENTS for the BALANCED ROUND ROBIN algorithm
The requirements of the algorithm can be defined by these four rules:
 1) All versus all
 Each team must meet exactly once, and once only, the other teams in the division league. 
 If the division is composed of n teams, the championship takes place in the n-1 rounds.
2) Alternations HOME / AWAY rule
The sequence of alternations HOME / AWAY matches for every teams in the division league, should be retained if possible. 
For any team in the division league at most once in the sequence of consecutive matches HAHA, occurs the BREAK of the rhythm, i.e. HH or AA match in the two consecutive rounds.
3) The rule of the last slot number
The team with the highest slot number must always be positioned in the last row of the grid. 
For each subsequent iteration the highest slot number of grid alternates left and right position; left column (home) and right (away).
The system used to compose the league schedule is "counter-clockwise circuit." 
In the construction of matches in one round of the championship, a division with an even number of teams. 
If in a division is present odd number of teams, it will be inserted a BYE/Dummy team in the highest slot number of grid/ring.
4) HH and AA are non-terminal and not initial
 Cadence HH or AA must never happen at the beginning or at the end of the of matches for any team in the division.
 Corrective inversion RULE performs only once, in the bottom line in the RING, LeftRight redundant inversion flip-flop RULE, so we will never obtain in the last two rounds CC or FF.
Round Robin ALGORITHM
The algorithm that satisfies rule (1) is obtained with a simple algorithm Round Robin:
where every successive round is obtained applying to the slot numbers ring a   "counterclockwise" rotation.
To satisfy the rule (2) we must "improve", the simple round robin algorithm by performing balancing of Home and Away sequence. 
It is performed by applying several "counterclockwise" rotations in the slot numbers ring in order to obtain acceptable combinations of slot positions for the next round.

The number of rotations required in the ring is (n / 2 -1).
So we will get that in the two successive rounds, almost all the teams playing at home in the previous round, will play away from home in the next round.
DATA STRUCTURE
n_teams: (4,6,8,..,20)
n_rounds:  n_teams -1;

Ring – Circuit Ring is such data structure, i.e. a particular type of sequence where are performable and formally algorithmically defined: operation of (anti-clockwise) ROTATION among ring elements and the operation INSERT_LAST_TEAM, The ring content defines all matches for the each particular round in match schedule Ring.Length is an even number equal to n_teams Left_ring sub-sequence: The Ring sub-sequence with elements from 1 to n/2. Right_ring sub-sequence: Ring sub-sequence with elements from n/2+1 to n. Match [i] = Ring_element [ i ] : Ring_element [ n – i + 1 ]; where i = 1 to n/2 The MATCH is an ordered pair composed of two TEAMS, (Home_team : Away_team). 1st Round Home : Away 01:07 02:06 03:05 04:08

Next_Iteration is obtained by applying these rules:
a)   perform (n/2 – 1) times * ANTI CLOCKWISE ROTATIONs  
b)   all right column elements, below the last team, will be shifted upwards 
c)   INSERT_LAST_TEAM 
(Insert_Last_Element_into_ Ring_onLeft (n) or 
 Insert_Last_Element_into_Ring_onRight(n), alternatively)
d.1) Last Line LeftRight redundant swap RULE 
eventually have to swap elements in the last row once again
d.1) last team left/right - flip/flop



In the following example it will be explained how the Ring elements of 8 teams 
are gradually transformed in five steps, 
from from the SECOND ROUND into the THIRD ROUND.
If we start from from the SECOND ROUND:
05 :04
06 :03
07 :02
08 :01
a. After we perform THREE Anti-clockwise rotations, (n =8, 3 = 8/2 -1)
we will get the situation like this:
02 :01
03 :08
04 :07
05 :06
b. When we apply the LAST SLOT RULE: 
the right column elements (06,07) below last team (08) will be shifted upwards
02 :01
03
04 :07
05 :06
c. And now we will apply the LAST SLOT RULE-bottom right, 
we will get the situation which describes the THIRD ROUND: 
(08 must be moved to the bottom right position)
02 :01
03 :07
04 :06
05 :08
d.1 Now it will be checked if for this iteration number (i.e. round) 
depending on CODE SIX or ZERO Cadence, we eventually have to 
swap elements in the last row redundantly,
Left/Right swaping
d.2 And at the end we will apply the LAST TEAM SLOT ROULE
swap left & right elements, 
if in the previous iteration last team was positioned on the right, 
in this iteration it should be positioned on the left bottom position, 
so the last line elements will be swapped, else do nothing.
THIRD ROUND:
02 :01
03 :07
04 :06
05 :08

read more

Here is the snippet of the code in Perl.