生成体育联赛的自然时间表 [英] Generating natural schedule for a sports league

问题描述

我正在寻找一种算法来为一组
的球队生成时间表。例如，想象一个运动季，每个团队互相比赛
，一次作为主队，另一次作为客队在另一个团队的
场上。

在本赛季中生成一组所有比赛很容易，如果球队是
球队名单，则可以执行以下操作：

  set（（x，y）for x in team for y in team if x！= y）
  

但我也想按
的时间顺序对游戏进行排序，以使其满足有效游戏时间表的约束，并且
看起来自然是随机的。 / p>

约束是，游戏列表应可分组为多个
个回合，其中每个回合包含n / 2个游戏（其中n是
个团队），其中每个团队都与另一个团队配对。

为使日程安排看起来更加自然，两支球队不应在连续回合中两次面对对方
。也就是说，如果（a，b）在一局
中进行游戏，则游戏（b，a）不应在下一局中进行。

另外，每支球队都应尽可能多地以每局客队
的价格进行比赛，而其他各轮则以主队的形式进行比赛。我认为
不可能总是满足此约束，因此
拥有东西会更好。例如，一支球队不应该玩8场主场比赛和
然后不玩8场客场比赛。

下面是我现在得到的。该算法的主要问题是
经常卡在while循环中。尤其是当
的团队数量为16个或更多时。这也是非常低效的，因为它
建立在使用随机样本函数并希望正确的基础上：

  from随机导入样本
 def season_schedule_order（团队，对）：
 n_games_per_round = len（团队）// 2 
 last_pairs = set（）
而对：
 r_pairs = set（sample（pairs，Pairs，n_games_per_round））
＃检查每个队伍在该回合中是否出现一次。 
 r_teams = set（x代表（x，y）在r_pairs中）| set（y为r_pairs中的（x，y）y）
如果r_teams！=团队：
继续
＃检查两个团队是否不再面对对方。 
 rev_pairs = set（（r，pair中（x，y）中的（x，y）为（y，x）））
如果rev_pairs& last_pairs：
继续
对-= r_pairs 
 for r_pairs中的p：
 yield p 
 last_pairs = r_pairs 
 
 team = set（[ 'aik'，'djurgarden'，'elfsborg'，'gais'，
'gefle'，'hacken'，'halmstad'，'helsingborg']）
对= set（（（x，y）对于x团队中的x，如果x！= y中的y中的y）
 for season_schedule_order（团队，对）中的（ht，at）：
打印'％-20s％-20s'％（ht，at ）
  

解决方案

我找到了此处，我对此略加修改：

  def round_robin（units，sets = None）：
根据单元列表生成合理配对的时间表 
 count = len（units）
组=组或（count-1）
一半=计数/ 2 
范围内的转弯（组）：
左=单位[：半] 
右=单位[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（））
收益配对
 
团队= ['a'，'b'，'c'，'d'] 
打印列表（round_robin（teams ，set = len（teams * * 2-2））
  

现在我只需要把它变成plpgsql。 ：）

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)

解决方案

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

这篇关于生成体育联赛的自然时间表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！