java - 联赛赛程的排列

Question

创建联赛日程安排软件并遇到一个数学问题，我需要一些帮助来解决这个问题。

假设您有 4 个团队(为简单起见)，您检查 1、2、3、4 的所有可能排列。此排列仅称为第一周，它为您提供 24 种可能的排列。

1,2,3,4 是一个排列，假设第 1 周 1X4 是一场比赛 2X3 是一场比赛。第二周的比赛组合是通过循环赛设定的，接下来是 4、1、2、3； 4X3 1X2 是游戏。

我的问题是，如果第二周的游戏组合不起作用(由于限制)，而是 3、4、1、2 的顺序可行，是否可以通过在第一周执行排列来检查？即第 1 周是 1,2,3,4，第 2 周是 3,4,1,2

或者我是否需要排列第 1 周，然后排列第 2 周等等，以实际获得所有可能的时间表。我的直觉告诉我，我确实需要每周排列一次，以便真正获得时间表的所有可能排列。

编辑:我想问是否有四个星期我的排列计算器会是 24*24*24*24 而不仅仅是 24。

Answer 1

直接回答您的问题，仅检查第 1 周的所有排列不一定会检查所有可能的排列。用一些简单的样本进行测试，您很快就会发现这一点

在我看来你需要一个标准的 Backtracking算法。这些专为具有约束的这些类型的问题而设计。

一般形式是这样的

function permutation
    if all current matches satisfy constraints
        if any weeks remaining to be allocated
            for each possible match for next week
                call permutation with that match added
        else
            accept this solution

假设有足够多的约束，很少有排列是合法的。然而，如果许多排列是合法的，那么接受解决方案的过程将需要在处理它们的方式时考虑到这一点。