This is not really a combinatorial problem, I'll use small letters
instead of caps.
Arrange the r referees in a circle.
start <- 1
Replicate k times{
end <- (start + m-1)%% r
output: c(start,end)
start <- (end+1)%% r
}
Bert Gunter
Genentech Nonclinical Biostatistics
(650) 467-7374
"Data is not information. Information is not knowledge. And knowledge
is certainly not wisdom."
H. Gilbert Welch
On Wed, Apr 30, 2014 at 10:48 AM, Ravi Varadhan <ravi.varad...@jhu.edu> wrote:
> 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
>
>
> [[alternative HTML version deleted]]
>
> ______________________________________________
> 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.
______________________________________________
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.
