PHP

Question

我有以下九支队伍参加一项活动：

array('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I')

本次活动每场比赛需要三支队伍参赛（即：A vs B vs C）。每支球队都需要与其他球队比赛一次，而且只需要一次。

以上九支队伍共进行四轮比赛（每支球队每场比赛与另外两支球队比赛，每支球队有八支球队进行比赛 - 8 / 2 = 4轮）共十二场比赛在所有四轮比赛中（每轮有三场比赛，每场比赛三支球队 - 4 轮 x 3 场比赛 = 总共 12 场比赛）。

我期望的输出格式是：

array('A', 'B', 'C')
array('D', 'E', 'F')
array('G', 'H', 'I')
etc...

以上一共是十二个数组。

您如何将上述九支球队分布在十二个单独的阵列中（每个阵列代表一场比赛），以便每支球队与其他球队只比赛一次？

Answer 1

这类问题属于设计理论。我认为在这种情况下所谓的斯坦纳系统 S(2,3,9)

123, 456, 789, 147, 258, 369, 159、267、348、168、249 和 357。

我从 http://users.mct.open.ac.uk/mjg47/papers/IntroSteiner.pdf 剪切和粘贴的地方希望避免拼写错误。

（该理论是大量技巧和特殊情况的集合。我不知道总能找到答案并涵盖所有情况的通用算法）

Answer 2

另一种方法是将其视为约束系统。这样的问题可以用约束求解器来解决。这个问题有时被称为社交高尔夫球手问题（Google 会找到很多参考资料）。数学模型可能如下所示：

指数：

  t in {A,..,I}  (team)
  r in {round1,..,round4}
  m in {match1,..,match3}

二进制变量：

x(r,m,t) in {0,1}  (indicates if team t plays in round r, match m)

限制条件：

sum(m,x(r,m,t)) = 1 for all r,t                    (team plays exactly once in a round)
sum(t,x(r,m,t)) = 3 for all r,m                    (three teams in a match)  
sum((r,m), x(r,m,t1)*x(r,m,t2)) <= 1 for all t1<t2 (teams play once in same match)

这可以使用约束求解器或 MIQCP（混合整数二次约束规划）求解器来解决。（在后一种情况下添加一个虚拟 objective）。最后一个二次约束可以线性化，在这种情况下我们也可以使用线性 MIP（混合整数规划）求解器来求解。

我的解决方案如下：

----     33 VARIABLE x.L  

                        A           B           C           D           E           F           G           H           I

round1.match1                       1                                                           1           1
round1.match2                                   1                                   1                                   1
round1.match3           1                                   1           1
round2.match1           1                                                           1           1
round2.match2                       1                       1                                                           1
round2.match3                                   1                       1                                   1
round3.match1                       1                                   1           1
round3.match2           1                                                                                   1           1
round3.match3                                   1           1                                   1
round4.match1           1           1           1
round4.match2                                               1                       1                       1
round4.match3                                                           1                       1                       1

PHP - 将团队平均分配到数组中，这样组合就不会重复

PHP - Evenly Distribute Teams Into Arrays So That No Combination Repeats

algorithm

combinations

schedule

permutation