使用随机数生成器时,如何减少人员被随机分配到同一团队的次数?

机器算法验证 算法 随机生成
2022-03-31 18:36:22

我每周随机分配人们参加不同的高尔夫球队。我有 7 支球队,每支球队有 4 名球员。

我的起始名单按姓氏字母顺序排列。

我使用基于大气噪声的随机数生成器每周分配人员。但是,我确实连续几周将人们聚集在同一个团队中。

如何减少 2 人或更多人被随机分配到同一团队的次数?我应该随机化起始名单然后随机化团队吗?

1个回答

你的问题似乎是双重的:当他们连续两周(轮次)有一个共同的伴侣时,人们会注意到。当他们经常有共同的伴侣时,他们也会注意到。事实证明,限制前一种可能性也会使后一种比率保持在较低水平。所以,让我们解决第一个问题。

一个快速简单的解决方案是拒绝抽样。 它在这里的工作方式是将一轮的分配设想为所有可能分配的随机样本(其中有超过),一组 在任意数量轮之后,假设您已经根据前几轮的结果为每个可能的分配指定了选择概率。为了生成下一轮的团队分配,您反复 ,将其选择概率与随机生成的概率时接受该分配。1016Ω.rωΩ,Pr(ω)U,Uω.

也许最简单的例子是将选择概率设置为零,以便将两个刚刚在上一轮中一起比赛的队友配对。该算法要么不会终止(因为不可能随机选择满足您的标准),要么会产生令人满意的分配。以下是此类时间表的前两轮示例,显示了(随机)选择ω

, , Round = 1

      Team
        1  2  3  4  5  6  7
  [1,]  4 15  6  3  1  2 11
  [2,]  5 16 13  8  7 14 12
  [3,]  9 24 18 19 10 22 23
  [4,] 25 27 21 20 17 26 28

, , Round = 2

      Team
        1  2  3  4  5  6  7
  [1,]  3  2 16  6  9  1 10
  [2,]  5  8 17 11 19  4 20
  [3,]  7 12 18 15 26 21 23
  [4,] 14 13 25 22 27 28 24

您可以通过检查来检查在第一轮中组队的人在第二轮中没有再次组队。

另一个版本是跟踪过去每对人的合作频率,并减少与这些频率成反比的选择概率。这是将同一团队的任务分配率降至最低的一种方法,但其本身并不能解决连续两周拥有共同合作伙伴的第一个问题。

这是最简单程序的结果摘要,运行 52 轮。

数字

对从未一起玩过,对一起玩过一次,对一起玩过两次,……,还有对在 52 轮中的 13 轮中一起玩过。当然,从结构上讲,没有人会连续两轮有一个共同的队友。616381

平均而言,每个人与任何特定的其他人一起玩不到六次(因为一个团队中有个其他人可用,其他人,与某人组队的平均机会等于每轮;和 ) 这些对计数的分布与速率为 这种关系可以在您生成计划之前预测对数的分布。281=2741=33/27=1/952/9<6.52/9.

这种方法的另一个不错的特点是它是“在线的”,因为您可以应用它而无需任何修改,以扩展现有的计划。


R代码生成示例和图形。

pick <- function(n, k) matrix(sample.int(n*k, n*k), n)
evaluate <- function(X, A) max(apply(X, 1, function(x) max(A[x, x]))) > 0
update <- function(X, A) {
  I <- t(matrix(apply(X, 1, combn, m=2), 2))
  A[I] <- A[I] + 1 # Increment pair counts
  A
}    
n <- 7                   # Number of teams
k <- 4                   # Players per team
N <- 52                  # Number of rounds to schedule
A <- matrix(0, k*n, k*n) # Tracks the pairings from the previous round
Schedule <- array(NA, c(k, n, N), dimnames=list(Position=1:k, Team=1:n, Round=1:N))
set.seed(17)
for (round in 1:N) {
  while(evaluate(X <- pick(n, k), A)) {} # Rejection sampling
  A <- update(X, matrix(0, k*n, k*n))    # Record the results for future selections
  Schedule[,,round] <- t(X)              # Save this assignment in the schedule
}
Schedule2 <- apply(Schedule, c(2,3), sort) # Make the schedule easier to read
(Schedule2[,,1:2])                         # Inspect it
#
# Plot a summary of this schedule.
#
check <- function(Schedule) {
  stopifnot(unique(apply(Schedule, 3, function(x) length(unique(c(x))))) == n*k)
  Pairs <- matrix(apply(Schedule, 3, function(S) apply(S, 2, combn, m=2)), 2)
  A <- table(Pairs[1, ], Pairs[2, ])
  table(A[lower.tri(A)] + t(A)[lower.tri(A)])
}
y <- c(check(Schedule))
i <- as.numeric(names(y))
plot(i, y, type="h", lwd=2, ylim=c(0, max(y)),
     main=paste("Common Teammate Frequencies in", N, "Rounds"))