我正在尝试创建一些伪代码,以生成此场景的可能结果:
有一个比赛正在进行,每一轮比赛中的所有球员都是同一组,其他球员来自不同的球队。
给定x个队,每个队正好有n个队员。对于r码的球队,你只能有一名球员,而球员必须在前几轮中没有和其他球员一起比赛,那么可能的结果是什么。
示例:4个队(a-d),每个队4名队员,每组4名队员。
可能的分组是:(正确的团队约束)
A1, B1, C1, D1
A1, B3, C1, D2
但不是:(违反同一团队约束)
A1, A3, C2, D2
B3, C2, D4, B1
但是,唯一性约束在这个分组中起作用
A1, B1, C1, D1
A1, B3, C1, D2
虽然它确实遵循了与不同球队比赛的限制,但它打破了与不同球员比赛的唯一性规则在这种情况下,A1与C1分为两组
最后,伪代码应该能够创建如下内容
Round 1 Round 2 Round 3 Round 4
a1 b1 a1 d4 a1 c2 a1 c4
c1 d1 b2 c3 b4 d3 d2 b3
a2 b2 a2 d1 a2 c3 a2 c1
c2 d2 b3 c4 b1 d4 d3 b4
a3 b3 a3 d2 a3 c4 a3 c2
c3 d3 b4 c1 b2 d1 d4 b1
a4 b4 a4 d3 a4 c1 a4 c3
c4 d4 b1 c2 b3 d2 d1 b2
在这个例子中,你可以看到在每一轮中,没有一个玩家与前一个玩家分组。
最佳答案
如果团队中的玩家的数量是一个素数幂(2, 3, 4,5, 7, 8,9, 11, 13,16, 17, 19,等等),那么这里有一个算法,它基于有限仿射平面创建一个具有最大轮数的调度。
我们在有限域中工作,其中n是团队中的玩家数。GF(n)有自己的乘法概念,当n是素数时,它是乘法模n,当n是某素数的高次幂时,它是一元多项式的乘法模某个适当次的不可约多项式每个团队由gf(n)的一个非零元素标识;让团队标识集为t。每个团队成员由t×gf(n)中的一对标识。对于gf(n)的每个非零元素r,r轮的组是
{{(t, r*t + c) | t in T} | c in GF(n)},
其中
*
和+
分别表示gf(n)中的乘法和加法。GF
这个问题与Implementation in Python 3密切相关社交型高尔夫球手的问题是,如果n名球员每天在g组s(n=g×s)中打一次球,那么他们可以安排多少天,这样就不会有球员和其他球员一起打超过一次球了?
求解社交高尔夫问题实例的算法是约束解算器和数学结构的拼凑,它们一起并不能很好地解决很多问题如果一个团队中的玩家数量等于团队规模,那么可以通过将第一天的日程解释为团队任务,然后使用日程的其余部分来获得这个问题的解决方案可能还有其他结构。