保持双头背靠背的排序算法

Question

在运动日程安排的背景下，我有一个游戏列表，其中球队可能会玩超过 1 场比赛。如果是这样的话，他们的比赛应该是背靠背的。由于配对的性质，这可能不可行，至少它们应该尽可能靠近。

这是初始配对的示例，其中每个团队都玩 2x：

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

请注意，这不是每支球队在主客场比赛中每隔两场比赛的双循环赛制。这只是一个团队进行两场比赛的配置。

我正在尝试实施一种算法来对这些比赛进行排序，以使每支球队的比赛尽可能接近。这是第一个简单的方法：

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

这是结果：

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

显然这不是很好，因为它是一方面的，通过将他们的游戏放在列表的前面，它使列表末尾的团队受益更多。对于单边，我的意思是它在每场比赛中只看一支球队，并为那支球队进行排序，而忽略第二支球队，这将打破另一支球队的背靠背平衡。

这将是使用约束规划进行最大化的完美案例，例如使用 python-constraint or pyomo。但是我真的很不擅长建模约束满足问题 (CSP)，所以我不知道从哪里开始处理这个案例。

有什么想法吗？

Answer 1

递归函数可以尝试以动态编程方式进行各种排序，这种方式优先考虑连接的游戏而不是序列中的中断。

这个没有特别优化，但对于小的游戏列表应该足够快：

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

输出：

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

请注意，这可以确保尽可能多的球队连续比赛。如果您的目标是尽量减少任何球队比赛之间的最坏情况 'distance'，或尽量减少每支球队的平均比赛距离，这可能不是最佳解决方案。

保持双头背靠背的排序算法

Sorting algorithm to keep doubleheaders back-to-back

python

algorithm

sorting

constraints