为体育联赛生成自然赛程

Question

我在寻找一种算法，用来为一组球队生成比赛日程。比如，想象一下一个体育赛季，每支球队都要和其他球队比赛一次，作为主队和客队各一次。

生成整个赛季的比赛列表其实很简单，如果球队是一个球队的列表，可以用下面的方式来实现：

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

但我还想把这些比赛按时间顺序排列，并且要满足有效比赛日程的要求，同时看起来要“自然随机”。

这里的要求是，比赛列表应该可以分成若干轮，每轮有 n / 2 场比赛（n 是球队的数量），每场比赛中每支球队都要和另一支球队配对。

为了让日程看起来更自然，两个球队在连续的轮次中不应该互相对战。也就是说，如果在一轮中有 (a, b) 的比赛，那么在下一轮中就不应该有 (b, a) 的比赛。

此外，尽可能让每支球队在每隔一轮中作为客队比赛，而在其他轮次中作为主队比赛。我觉得这个要求不一定能总是满足，所以这只是一个希望能做到的目标。例如，一支球队不应该先打 8 场主场比赛，然后再打 8 场客场比赛。

下面是我现在的结果。这个算法的主要问题是，它在循环中经常会卡住，尤其是当球队数量达到 16 或更多时。而且它效率也很低，因为它依赖于随机抽样函数，希望能得到正确的结果：

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)

Answer 1

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;

环形结构 – 电路 环形是一种数据结构，也就是一种特定类型的序列。在这个序列中，可以进行一些特定的操作，这些操作是有明确算法定义的：比如在环形元素之间进行（逆时针方向的）旋转，以及在最后插入一个团队的操作。 环形的内容定义了比赛日程中每一轮的所有比赛。 环形的长度是一个偶数，等于参赛队伍的数量（n_teams）。 左环子序列：包含从1到n/2的元素的环形子序列。 右环子序列：包含从n/2+1到n的元素的环形子序列。 比赛[i] = 环形元素[i] : 环形元素[n – i + 1]；其中i的范围是从1到n/2。 一场比赛是由两个团队组成的有序对，格式是（主队 : 客队）。 第一轮 主队 : 客队 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

了解更多

这里有一段用Perl写的代码示例。

Answer 2

我在这里找到了一种方法这里，我稍微做了一些调整，变成了这样：

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))

现在我只需要把这个转换成plpgsql语言就可以了。 :)