随机地将元素重复分配给有限数量的组

Question

有N个组(也就是法官,比方说17个)和M个元素(让我们称之为案例,比方说22个),使得3*M <= 4*N.

N <- LETTERS[1:17]
M <- 1:22

我想给N个法官中的每一个分配4个或更少的案件,这样每个案件的评估不会多于或不少于3个法官,而且没有法官两次看同一案件.

A : 1, 2, 19
B : 2, 3, 8, 22
...
Q : 1, 2, 12, 10

在R中任何快速简便的方法吗？

到目前为止试过这个:

df <- data.frame(ID=rep(M,3))
values <- N
df$values[sample(1:nrow(df), nrow(df), FALSE)] <- rep(values, 4)

Answer 1

通常当我看到"随机分配受约束"问题时,我的想法是:

1. 选择一个随机权重,将项目i分配给类别j(在这种情况下,指定案例i来判断j)
2. 使用线性编程来识别满足所有约束的分配(<= 4个案例/判断和每个案例3个评论),具有最大权重.

这在R中非常简单,使用像lpSolve这样的线性编程包,创建一个二进制变量x_ij,指示我们是否为每个case/judge对分配case i来判断j:

library(lpSolve)
set.seed(144)
# vars is a convenience matrix that tells us the i and j index of each variable in our model
vars <- expand.grid(i=M, j=N)
mod <- lp(direction = "max",
          objective.in = rnorm(nrow(vars)),
          const.mat = rbind(t(sapply(M, function(i) as.numeric(vars$i == i))),
                            t(sapply(N, function(j) as.numeric(vars$j == j)))),
          const.dir = rep(c("=", "<="), c(length(M), length(N))),
          const.rhs = rep(c(3, 4), c(length(M), length(N))),
          all.bin = TRUE)

# Extract all cases assigned to each judge
sapply(N, function(j) vars$i[mod$solution > 0.999 & vars$j == j])
# $A
# [1]  2 10 15
# 
# $B
# [1]  7  8 13 22
# 
# $C
# [1] 2 3 7 9
# ...

顺便说一下,我们设置了权重和约束,这实际上可以被认为是从案例的所有可行分配到法官的随机选择.