> -----Original Message----- > From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-project.org] > On Behalf Of Ravi Varadhan > Sent: Wednesday, April 30, 2014 10:49 AM > To: r-help@r-project.org > Subject: [R] A combinatorial assignment problem > > Hi, > > I have this problem: K candidates apply for a job. There are R referees > available to review their resumes and provide feedback. Suppose that we > would like M referees to review each candidate (M < R). How would I > assign candidates to referees (or, conversely, referees to candidates)? > There are two important cases: (a) K > (R choose M) and (b) K < (R > chooses M). > > Case (a) actually reduces to case (b), so we only have to consider case > (b). Without any other constraints, the problem is quite easy to solve. > Here is an example that shows this. > > require(gtools) > set.seed(12345) > K <- 10 # number of candidates > R <- 7 # number of referees > M <- 3 # overlap, number of referees reviewing each candidate > > allcombs <- combinations(R, M, set=TRUE, repeats.allowed=FALSE) > assignment <- allcombs[sample(1:nrow(allcombs), size=K, replace=FALSE), ] > assignment > > assignment > [,1] [,2] [,3] > [1,] 3 4 5 > [2,] 3 5 7 > [3,] 5 6 7 > [4,] 3 5 6 > [5,] 1 6 7 > [6,] 1 2 7 > [7,] 1 4 5 > [8,] 3 6 7 > [9,] 2 4 5 > [10,] 4 5 7 > > > > Here each row stands for a candidate and the column stands for the > referees who review that candidate. > > Of course, there are some constraints that make the assignment > challenging. We would like to have an even distribution of the number of > candidates reviewed by each referee. For example, the above code produces > an assignment where referee #2 gets only 2 candidates and referee #5 gets > 7 candidates. We would like to avoid such uneven assignments. > > > table(assignment) > assignment > 1 2 3 4 5 6 7 > 3 2 4 4 7 4 6 > > > > Note that in this example there are 35 possible triplets of referees and > 10 candidates. Therefore, a perfectly even assignment is not possible. > > I tried some obvious, greedy search methods but they are not guaranteed to > work. Any hints or suggestions would be greatly appreciated. > > Best, > Ravi >
Well, if you don't need clever, a brute force approach could work (depending on the values of k, r, and m). Something like this assignment <- function(k,r,m,max_iter=120) { n <- 0 cmb <- combn(r,m) repeat { n <- n+1 tbl <- table(map<-cmb[,sample(1:choose(r,m),k)]) if(min(tbl) == max(tbl)-1) break if(n > max_iter) break } return(t(map)) } a <- assignment(10,7,3) Dan Daniel Nordlund Bothell, WA USA ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.