安排超过两个团队参与比赛的程序

huangapple
go评论64阅读模式
英文:

scheduling program for more than two teams per game

问题

我有一个关于调度问题的问题，类似于这个问题。

我想编写一个程序或算法来计算一个体育联赛的比赛日程，但不是每场比赛两个队，而是3个或更多个队。这里的约束是只要它能工作，没有“主场”和“客场”的区别，我只需要找到一个正确的比赛元组组合。我想通过一个9队联赛，每场比赛3队，来说明我的意思：

(0,1,2),(3,4,5),(6,7,8) - 第一比赛日
(0,1,3),(2,4,6),(5,7,8) - 第二比赛日
...
(0,7,8),(1,2,3),(4,5,6) - 可能是最后一场，在这种情况下是第28（8超2）比赛日

比赛的总场次是（n超过k），比赛日的总数是（（n-1）超过（k-1）），其中n是队伍数，k是每场比赛的队伍数。

你有没有想法如何编写这个程序，我已经在互联网上搜索过但没有找到任何东西。我也知道对于大的n，计算可能需要很长时间，但如果需要几天来计算的话也可以。首选编程语言将是Python，但我也接受C、C++或Java。

任何帮助都将不胜感激。在此先感谢你！

英文:

I have a question regarding a scheduling problem, similar to this problem .

I would like to write a program or algorithm to calculate a game schedule for a sports league, but not with two teams per game, rather than with 3 or more teams. The constraints I have here is only that it works, there's no "home" and "away" difference, I only need to find one correct combination of the game tuples. I want to show you what I mean with that with a 9 teams league with 3 teams per game:

(0,1,2),(3,4,5),(6,7,8) - First matchday
(0,1,3),(2,4,6),(5,7,8) - Second matchday
...
(0,7,8),(1,2,3),(4,5,6) - Might be the last, in this case 28th (8 over 2), matchday

the total number of games are (n over k), the total number of matchdays are ((n-1) over (k-1)), where n is the team number and k is the number of teams per game.

Do you have any ideas how to write this program, I already searched the internet but didn't find anything. I also know that for large n, the calculation might need very long, but it would be ok if it takes some days to calculate. Preferred programming language would be python, but I would also accept C, C++ or java.

Any help would be appreciated. Thank you already in advance!

答案1

得分: 0

这是代码示例，以下是翻译的内容：

这个并不太难，使用 itertools 很容易。要枚举，我们选择一个特定的竞争者来检查（在下面的代码中始终选择最小值，但这是任意选择），然后迭代所有可能的与该竞争者的组合，迭代其他竞争者的所有可能的分组，然后将它们组合在一起。

英文:

This isn’t too difficult with itertools. To enumerate, we choose a particular competitor to examine (always the minimum in the code below, but that’s an arbitrary selection), iterate over all possible groupings with that competitor, iterate over all possible partitions of the other competitors, and combine them.

import itertools


def partitions(s, k):
    s = set(s)
    assert len(s) % k == 0
    if s:
        x = min(s)
        s.remove(x)
        for c in itertools.combinations(sorted(s), k - 1):
            for p in partitions(s - set(c), k):
                yield [(x,) + c] + p
    else:
        yield []


if __name__ == "__main__":
    for q in partitions(range(9), 3):
        print(q)

Sample output:

[(0, 1, 2), (3, 4, 5), (6, 7, 8)]
[(0, 1, 2), (3, 4, 6), (5, 7, 8)]
[(0, 1, 2), (3, 4, 7), (5, 6, 8)]
[(0, 1, 2), (3, 4, 8), (5, 6, 7)]
[(0, 1, 2), (3, 5, 6), (4, 7, 8)]
[(0, 1, 2), (3, 5, 7), (4, 6, 8)]
[(0, 1, 2), (3, 5, 8), (4, 6, 7)]
[(0, 1, 2), (3, 6, 7), (4, 5, 8)]
[(0, 1, 2), (3, 6, 8), (4, 5, 7)]
[(0, 1, 2), (3, 7, 8), (4, 5, 6)]
[(0, 1, 3), (2, 4, 5), (6, 7, 8)]
[(0, 1, 3), (2, 4, 6), (5, 7, 8)]
[(0, 1, 3), (2, 4, 7), (5, 6, 8)]
[(0, 1, 3), (2, 4, 8), (5, 6, 7)]
[(0, 1, 3), (2, 5, 6), (4, 7, 8)]
[(0, 1, 3), (2, 5, 7), (4, 6, 8)]
[(0, 1, 3), (2, 5, 8), (4, 6, 7)]
[(0, 1, 3), (2, 6, 7), (4, 5, 8)]
[(0, 1, 3), (2, 6, 8), (4, 5, 7)]
[(0, 1, 3), (2, 7, 8), (4, 5, 6)]
[(0, 1, 4), (2, 3, 5), (6, 7, 8)]
[(0, 1, 4), (2, 3, 6), (5, 7, 8)]
[(0, 1, 4), (2, 3, 7), (5, 6, 8)]
[(0, 1, 4), (2, 3, 8), (5, 6, 7)]
[(0, 1, 4), (2, 5, 6), (3, 7, 8)]
[(0, 1, 4), (2, 5, 7), (3, 6, 8)]
[(0, 1, 4), (2, 5, 8), (3, 6, 7)]
[(0, 1, 4), (2, 6, 7), (3, 5, 8)]
[(0, 1, 4), (2, 6, 8), (3, 5, 7)]
[(0, 1, 4), (2, 7, 8), (3, 5, 6)]
[(0, 1, 5), (2, 3, 4), (6, 7, 8)]
[(0, 1, 5), (2, 3, 6), (4, 7, 8)]
[(0, 1, 5), (2, 3, 7), (4, 6, 8)]
[(0, 1, 5), (2, 3, 8), (4, 6, 7)]
[(0, 1, 5), (2, 4, 6), (3, 7, 8)]
[(0, 1, 5), (2, 4, 7), (3, 6, 8)]
[(0, 1, 5), (2, 4, 8), (3, 6, 7)]
[(0, 1, 5), (2, 6, 7), (3, 4, 8)]
[(0, 1, 5), (2, 6, 8), (3, 4, 7)]
[(0, 1, 5), (2, 7, 8), (3, 4, 6)]
[(0, 1, 6), (2, 3, 4), (5, 7, 8)]
[(0, 1, 6), (2, 3, 5), (4, 7, 8)]
[(0, 1, 6), (2, 3, 7), (4, 5, 8)]
[(0, 1, 6), (2, 3, 8), (4, 5, 7)]
[(0, 1, 6), (2, 4, 5), (3, 7, 8)]
[(0, 1, 6), (2, 4, 7), (3, 5, 8)]
[(0, 1, 6), (2, 4, 8), (3, 5, 7)]
[(0, 1, 6), (2, 5, 7), (3, 4, 8)]
[(0, 1, 6), (2, 5, 8), (3, 4, 7)]
[(0, 1, 6), (2, 7, 8), (3, 4, 5)]
[(0, 1, 7), (2, 3, 4), (5, 6, 8)]
[(0, 1, 7), (2, 3, 5), (4, 6, 8)]
[(0, 1, 7), (2, 3, 6), (4, 5, 8)]
[(0, 1, 7), (2, 3, 8), (4, 5, 6)]
[(0, 1, 7), (2, 4, 5), (3, 6, 8)]
[(0, 1, 7), (2, 4, 6), (3, 5, 8)]
[(0, 1, 7), (2, 4, 8), (3, 5, 6)]
[(0, 1, 7), (2, 5, 6), (3, 4, 8)]
[(0, 1, 7), (2, 5, 8), (3, 4, 6)]
[(0, 1, 7), (2, 6, 8), (3, 4, 5)]
[(0, 1, 8), (2, 3, 4), (5, 6, 7)]
[(0, 1, 8), (2, 3, 5), (4, 6, 7)]
[(0, 1, 8), (2, 3, 6), (4, 5, 7)]
[(0, 1, 8), (2, 3, 7), (4, 5, 6)]
[(0, 1, 8), (2, 4, 5), (3, 6, 7)]
[(0, 1, 8), (2, 4, 6), (3, 5, 7)]
[(0, 1, 8), (2, 4, 7), (3, 5, 6)]
[(0, 1, 8), (2, 5, 6), (3, 4, 7)]
[(0, 1, 8), (2, 5, 7), (3, 4, 6)]
[(0, 1, 8), (2, 6, 7), (3, 4, 5)]
[(0, 2, 3), (1, 4, 5), (6, 7, 8)]
[(0, 2, 3), (1, 4, 6), (5, 7, 8)]
[(0, 2, 3), (1, 4, 7), (5, 6, 8)]
[(0, 2, 3), (1, 4, 8), (5, 6, 7)]
[(0, 2, 3), (1, 5, 6), (4, 7, 8)]
[(0, 2, 3), (1, 5, 7), (4, 6, 8)]
[(0, 2, 3), (1, 5, 8), (4, 6, 7)]
[(0, 2, 3), (1, 6, 7), (4, 5, 8)]
[(0, 2, 3), (1, 6, 8), (4, 5, 7)]
[(0, 2, 3), (1, 7, 8), (4, 5, 6)]
[(0, 2, 4), (1, 3, 5), (6, 7, 8)]
[(0, 2, 4), (1, 3, 6), (5, 7, 8)]
[(0, 2, 4), (1, 3, 7), (5, 6, 8)]
[(0, 2, 4), (1, 3, 8), (5, 6, 7)]
[(0, 2, 4), (1, 5, 6), (3, 7, 8)]
[(0, 2, 4), (1, 5, 7), (3, 6, 8)]
[(0, 2, 4), (1, 5, 8), (3, 6, 7)]
[(0, 2, 4), (1, 6, 7), (3, 5, 8)]
[(0, 2, 4), (1, 6, 8), (3, 5, 7)]
[(0, 2, 4), (1, 7, 8), (3, 5, 6)]
[(0, 2, 5), (1, 3, 4), (6, 7, 8)]
[(0, 2, 5), (1, 3, 6), (4, 7, 8)]
[(0, 2, 5), (1, 3, 7), (4, 6, 8)]
[(0, 2, 5), (1, 3, 8), (4, 6, 7)]
[(0, 2, 5), (1, 4, 6), (3, 7, 8)]
[(0, 2, 5), (1, 4, 7), (3, 6, 8)]
[(0, 2, 5), (1, 4, 8), (3, 6, 7)]
[(0, 2, 5), (1, 6, 7), (3, 4, 8)]
[(0, 2, 5), (1, 6, 8), (3, 4, 7)]
[(0, 2, 5), (1, 7, 8), (3, 4, 6)]
[(0, 2, 6), (1, 3, 4), (5, 7, 8)]
[(0, 2, 6), (1, 3, 5), (4, 7, 8)]
[(0, 2, 6), (1, 3, 7), (4, 5, 8)]
[(0, 2, 6), (1, 3, 8), (4, 5, 7)]
[(0, 2, 6), (1, 4, 5), (3, 7, 8)]
[(0, 2, 6), (1, 4, 7), (3, 5, 8)]
[(0, 2, 6), (1, 4, 8), (3, 5, 7)]
[(0, 2, 6), (1, 5, 7), (3, 4, 8)]
[(0, 2, 6), (1, 5, 8), (3, 4, 7)]
[(0, 2, 6), (1, 7, 8), (3, 4, 5)]
[(0, 2, 7), (1, 3, 4), (5, 6, 8)]
[(0, 2, 7), (1, 3, 5), (4, 6, 8)]
[(0, 2, 7), (1, 3, 6), (4, 5, 8)]
[(0, 2, 7), (1, 3, 8), (4, 5, 6)]
[(0, 2, 7), (1, 4, 5), (3, 6, 8)]
[(0, 2, 7), (1, 4, 6), (3, 5, 8)]
[(0, 2, 7), (1, 4, 8), (3, 5, 6)]
[(0, 2, 7), (1, 5, 6), (3, 4, 8)]
[(0, 2, 7), (1, 5, 8), (3, 4, 6)]
[(0, 2, 7), (1, 6, 8), (3, 4, 5)]
[(0, 2, 8), (1, 3, 4), (5, 6, 7)]
[(0, 2, 8), (1, 3, 5), (4, 6, 7)]
[(0, 2, 8), (1, 3, 6), (4, 5, 7)]
[(0, 2, 8), (1, 3, 7), (4, 5, 6)]
[(0, 2, 8), (1, 4, 5), (3, 6, 7)]
[(0, 2, 8), (1, 4, 6), (3, 5, 7)]
[(0, 2, 8), (1, 4, 7), (3, 5, 6)]
[(0, 2, 8), (1, 5, 6), (3, 4, 7)]
[(0, 2, 8), (1, 5, 7), (3, 4, 6)]
[(0, 2, 8), (1, 6, 7), (3, 4, 5)]
[(0, 3, 4), (1, 2, 5), (6, 7, 8)]
[(0, 3, 4), (1, 2, 6), (5, 7, 8)]
[(0, 3, 4), (1, 2, 7), (5, 6, 8)]
[(0, 3, 4), (1, 2, 8), (5, 6, 7)]
[(0, 3, 4), (1, 5, 6), (2, 7, 8)]
[(0, 3, 4), (1, 5, 7), (2, 6, 8)]
[(0, 3, 4), (1, 5, 8), (2, 6, 7)]
[(0, 3, 4), (1, 6, 7), (2, 5, 8)]
[(0, 3, 4), (1, 6, 8), (2, 5, 7)]
[(0, 3, 4), (1, 7, 8), (2, 5, 6)]
[(0, 3, 5), (1, 2, 4), (6, 7, 8)]
[(0, 3, 5), (1, 2, 6), (4, 7, 8)]
[(0, 3, 5), (1, 2, 7), (4, 6, 8)]
[(0, 3, 5), (1, 2, 8), (4, 6, 7)]
[(0, 3, 5), (1, 4, 6), (2, 7, 8)]
[(0, 3, 5), (1, 4, 7), (2, 6, 8)]
[(0, 3, 5), (1, 4, 8), (2, 6, 7)]
[(0, 3, 5), (1, 6, 7), (2, 4, 8)]
[(0, 3, 5), (1, 6, 8), (2, 4, 7)]
[(0, 3, 5), (1, 7, 8), (2, 4, 6)]
[(0, 3, 6), (1, 2, 4), (5, 7, 8)]
[(0, 3, 6), (1, 2, 5), (4, 7, 8)]
[(0, 3, 6), (1, 2, 7), (4, 5, 8)]
[(0, 3, 6), (1, 2, 8), (4, 5, 7)]
[(0, 3, 6), (1, 4, 5), (2, 7, 8)]
[(0, 3, 6), (1, 4, 7), (2, 5, 8)]
[(0, 3, 6), (1, 4, 8), (2, 5, 7)]
[(0, 3, 6), (1, 5, 7), (2, 4, 8)]
[(0, 3, 6), (1, 5, 8), (2, 4, 7)]
[(0, 3, 6), (1, 7, 8), (2, 4, 5)]
[(0, 3, 7), (1, 2, 4), (5, 6, 8)]
[(0, 3, 7), (1, 2, 5), (4, 6, 8)]
[(0, 3, 7), (1, 2, 6), (4, 5, 8)]
[(0, 3, 7), (1, 2, 8), (4, 5, 6)]
[(0, 3, 7), (1, 4, 5), (2, 6, 8)]
[(0, 3, 7), (1, 4, 6), (2, 5, 8)]
[(0, 3, 7), (1, 4, 8), (2, 5, 6)]
[(0, 3, 7), (1, 5, 6), (2, 4, 8)]
[(0, 3, 7), (1, 5, 8), (2, 4, 6)]
[(0, 3, 7), (1, 6, 8), (2, 4, 5)]
[(0, 3, 8), (1, 2, 4), (5, 6, 7)]
[(0, 3, 8), (1, 2, 5), (4, 6, 7)]
[(0, 3, 8), (1, 2, 6), (4, 5, 7)]
[(0, 3, 8), (1, 2, 7), (4, 5, 6)]
[(0, 3, 8), (1, 4, 5), (2, 6, 7)]
[(0, 3, 8), (1, 4, 6), (2, 5, 7)]
[(0, 3, 8), (1, 4, 7), (2, 5, 6)]
[(0, 3, 8), (1, 5, 6), (2, 4, 7)]
[(0, 3, 8), (1, 5, 7), (2, 4, 6)]
[(0, 3, 8), (1, 6, 7), (2, 4, 5)]
[(0, 4, 5), (1, 2, 3), (6, 7, 8)]
[(0, 4, 5), (1, 2, 6), (3, 7, 8)]
[(0, 4, 5), (1, 2, 7), (3, 6, 8)]
[(0, 4, 5), (1, 2, 8), (3, 6, 7)]
[(0, 4, 5), (1, 3, 6), (2, 7, 8)]
[(0, 4, 5), (1, 3, 7), (2, 6, 8)]
[(0, 4, 5), (1, 3, 8), (2, 6, 7)]
[(0, 4, 5), (1, 6, 7), (2, 3, 8)]
[(0, 4, 5), (1, 6, 8), (2, 3, 7)]
[(0, 4, 5), (1, 7, 8), (2, 3, 6)]
[(0, 4, 6), (1, 2, 3), (5, 7, 8)]
[(0, 4, 6), (1, 2, 5), (3, 7, 8)]
[(0, 4, 6), (1, 2, 7), (3, 5, 8)]
[(0, 4, 6), (1, 2, 8), (3, 5, 7)]
[(0, 4, 6), (1, 3, 5), (2, 7, 8)]
[(0, 4, 6), (1, 3, 7), (2, 5, 8)]
[(0, 4, 6), (1, 3, 8), (2, 5, 7)]
[(0, 4, 6), (1, 5, 7), (2, 3, 8)]
[(0, 4, 6), (1, 5, 8), (2, 3, 7)]
[(0, 4, 6), (1, 7, 8), (2, 3, 5)]
[(0, 4, 7), (1, 2, 3), (5, 6, 8)]
[(0, 4, 7), (1, 2, 5), (3, 6, 8)]
[(0, 4, 7), (1, 2, 6), (3, 5, 8)]
[(0, 4, 7), (1, 2, 8), (3, 5, 6)]
[(0, 4, 7), (1, 3, 5), (2, 6, 8)]
[(0, 4, 7), (1, 3, 6), (2, 5, 8)]
[(0, 4, 7), (1, 3, 8), (2, 5, 6)]
[(0, 4, 7), (1, 5, 6), (2, 3, 8)]
[(0, 4, 7), (1, 5, 8), (2, 3, 6)]
[(0, 4, 7), (1, 6, 8), (2, 3, 5)]
[(0, 4, 8), (1, 2, 3), (5, 6, 7)]
[(0, 4, 8), (1, 2, 5), (3, 6, 7)]
[(0, 4, 8), (1, 2, 6), (3, 5, 7)]
[(0, 4, 8), (1, 2, 7), (3, 5, 6)]
[(0, 4, 8), (1, 3, 5), (2, 6, 7)]
[(0, 4, 8), (1, 3, 6), (2, 5, 7)]
[(0, 4, 8), (1, 3, 7), (2, 5, 6)]
[(0, 4, 8), (1, 5, 6), (2, 3, 7)]
[(0, 4, 8), (1, 5, 7), (2, 3, 6)]
[(0, 4, 8), (1, 6, 7), (2, 3, 5)]
[(0, 5, 6), (1, 2, 3), (4, 7, 8)]
[(0, 5, 6), (1, 2, 4), (3, 7, 8)]
[(0, 5, 6), (1, 2, 7), (3, 4, 8)]
[(0, 5, 6), (1, 2, 8), (3, 4, 7)]
[(0, 5, 6), (1, 3, 4), (2, 7, 8)]
[(0, 5, 6), (1, 3, 7), (2, 4, 8)]
[(0, 5, 6), (1, 3, 8), (2, 4, 7)]
[(0, 5, 6), (1, 4, 7), (2, 3, 8)]
[(0, 5, 6), (1, 4, 8), (2, 3, 7)]
[(0, 5, 6), (1, 7, 8), (2, 3, 4)]
[(0, 5, 7), (1, 2, 3), (4, 6, 8)]
[(0, 5, 7), (1, 2, 4), (3, 6, 8)]
[(0, 5, 7), (1, 2, 6), (3, 4, 8)]
[(0, 5, 7), (1, 2, 8), (3, 4, 6)]
[(0, 5, 7), (1, 3, 4), (2, 6, 8)]
[(0, 5, 7), (1, 3, 6), (2, 4, 8)]
[(0, 5, 7), (1, 3, 8), (2, 4, 6)]
[(0, 5, 7), (1, 4, 6), (2, 3, 8)]
[(0, 5, 7), (1, 4, 8), (2, 3, 6)]
[(0, 5, 7), (1, 6, 8), (2, 3, 4)]
[(0, 5, 8), (1, 2, 3), (4, 6, 7)]
[(0, 5, 8), (1, 2, 4), (3, 6, 7)]
[(0, 5, 8), (1, 2, 6), (3, 4, 7)]
[(0, 5, 8), (1, 2, 7), (3, 4, 6)]
[(0, 5, 8), (1, 3, 4), (2, 6, 7)]
[(0, 5, 8), (1, 3, 6), (2, 4, 7)]
[(0, 5, 8), (1, 3, 7), (2, 4, 6)]
[(0, 5, 8), (1, 4, 6), (2, 3, 7)]
[(0, 5, 8), (1, 4, 7), (2, 3, 6)]
[(0, 5, 8), (1, 6, 7), (2, 3, 4)]
[(0, 6, 7), (1, 2, 3), (4, 5, 8)]
[(0, 6, 7), (1, 2, 4), (3, 5, 8)]
[(0, 6, 7), (1, 2, 5), (3, 4, 8)]
[(0, 6, 7), (1, 2, 8), (3, 4, 5)]
[(0, 6, 7), (1, 3, 4), (2, 5, 8)]
[(0, 6, 7), (1, 3, 5), (2, 4, 8)]
[(0, 6, 7), (1, 3, 8), (2, 4, 5)]
[(0, 6, 7), (1, 4, 5), (2, 3, 8)]
[(0, 6, 7), (1, 4, 8), (2, 3, 5)]
[(0, 6, 7), (1, 5, 8), (2, 3, 4)]
[(0, 6, 8), (1, 2, 3), (4, 5, 7)]
[(0, 6, 8), (1, 2, 4), (3, 5, 7)]
[(0, 6, 8), (1, 2, 5), (3, 4, 7)]
[(0, 6, 8), (1, 2, 7), (3, 4, 5)]
[(0, 6, 8), (1, 3, 4), (2, 5, 7)]
[(0, 6, 8), (1, 3, 5), (2, 4, 7)]
[(0, 6, 8), (1, 3, 7), (2, 4, 5)]
[(0, 6, 8), (1, 4, 5), (2, 3, 7)]
[(0, 6, 8), (1, 4, 7), (2, 3, 5)]
[(0, 6, 8), (1, 5, 7), (2, 3, 4)]
[(0, 7, 8), (1, 2, 3), (4, 5, 6)]
[(0, 7, 8), (1, 2, 4), (3, 5, 6)]
[(0, 7, 8), (1, 2, 5), (3, 4, 6)]
[(0, 7, 8), (1, 2, 6), (3, 4, 5)]
[(0, 7, 8), (1, 3, 4), (2, 5, 6)]
[(0, 7, 8), (1, 3, 5), (2, 4, 6)]
[(0, 7, 8), (1, 3, 6), (2, 4, 5)]
[(0, 7, 8), (1, 4, 5), (2, 3, 6)]
[(0, 7, 8), (1, 4, 6), (2, 3, 5)]
[(0, 7, 8), (1, 5, 6), (2, 3, 4)]

huangapple
  • 本文由 发表于 2023年5月17日 16:11:09
  • 转载请务必保留本文链接：https://go.coder-hub.com/76269875.html
  • algorithm
  • scheduling
  • sports-league-scheduling-problem
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定