为体育联盟创造自然时间表

Question

我正在寻找一种算法来为一组团队生成一个时间表.例如,想象一个体育赛季,每个球队互相比赛,一次作为主队,另一个作为另一支球队的球队.

要在赛季中生成一组所有游戏很容易,如果团队是以下团队的列表:

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

但是我也希望按照时间顺序对游戏进行排序,使其满足有效游戏时间表的约束并且看起来"自然随机".

约束条件是游戏列表应该可分组为多轮,其中每轮包含n/2个游戏(其中n是团队数量),其中每个团队与另一个团队配对.

为了使赛程看起来更自然,两队不应连续两轮面对对方.也就是说,如果(a,b)在一轮中进行,则游戏(b,a)不应该在分机中进行.

此外,每支球队应尽可能多地作为客场球队和其他球队作为主队进行比赛.我认为不可能总是满足这个约束,所以拥有它更好.例如,一支球队不应该打8场主场比赛,然后打8场客场比赛.

以下是我现在得到的.该算法的主要问题是它经常陷入while循环.特别是当团队数量为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

我在这里找到了一种方法 ，我对此做了一些调整：

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