代码之家 › 专栏 › 技术社区 › Lloyd Banks

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

schedule permutation combinations algorithm php

-3

Lloyd Banks · 技术社区 · 6 年前

我有以下九支队伍参加一个活动:

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

对于上述九支球队,将有四轮(每支球队每场比赛将与另外两支球队比赛,每支球队有八支球队参加-8/2=4轮)和总共十二场比赛(每轮有三支球队的三场比赛-4轮x 3场比赛=12场总比赛)。

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

2 回复 | 直到 6 年前

mcdowella 6 年前

这类问题属于设计理论范畴。我认为在这种情况下,什么叫做斯坦纳系统S(2,3,9)

123, 456, 789, 147, 258, 369,

http://users.mct.open.ac.uk/mjg47/papers/IntroSteiner.pdf 希望能避免拼写错误。

(这个理论收集了大量的技巧和特例。我不知道有什么通用的算法总是能找到答案,并且能覆盖所有的情况)

Erwin Kalvelagen 6 年前

另一种方法是将其视为一个约束系统。这样的问题可以用约束求解器来解决。这个问题有时被称为 (谷歌会找到很多参考资料)。数学模型可以如下所示:

指数:

  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(混合整数二次约束规划)求解器来解决(在后一种情况下,添加一个虚拟目标)。最后一个二次约束可以线性化,在这种情况下,我们也可以用线性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