Re: [R] A combinatorial assignment problem
Ravi Varadhan jhu.edu> writes:
>
> Thanks, Bert.
> I have written this simple code, which is crude, but seems to do a decent
job. It works perfectly when M is a
> factor of R. Otherwise, it gives decent balance (of course, balance is not
guaranteed). I guess it is
> possible to take the results, that are somewhat unbalanced and then
reshuffle it semi-randomly to get
> better balance. Any improvements are appreciated!
>
> assign <- function(K, R, M, iseed=1234) {
> assignment <- matrix(NA, K, M)
> N <- R %/% M
> Nrem <- R %% M
> iseq <- seq(1,K,N)
> for (i in iseq){
> size <- ifelse(K-i >= N, R-Nrem, M*(K-i+1))
> sel <- sample(1:R, size=size, replace=FALSE)
> end <- min((i+N-1),K)
> assignment[i:end, ] <- sel
> }
> assignment
> }
>
> sol <- assign(40,16,3)
> table(sol)
>
> Thanks,
> Ravi
>
crossdes::find.BIB() seems to do better wrt balance and 'mixing' than
assign().
If you consider the usage of pairs of reviewers in this case,
find.BIB() comes closer to equal usage.
> assgn <- t(apply(assign(40,16,3),1,sort))
> bib <- find.BIB(16,40,3)
> adf <- data.frame(r1=factor(assgn[,c(1,1,2)],1:16),
+r2 = factor(assgn[,c(2,3,3)],1:16))
> bdf <- data.frame(r1=factor(bib[,c(1,1,2)],1:16),
+ r2 = factor(bib[,c(2,3,3)],1:16))
> table(xtabs(~.,adf)[upper.tri(diag(16))])
0 1 2 3 4
44 42 26 6 2
> table(xtabs(~.,bdf)[upper.tri(diag(16))])
0 1 2
5 110 5
>
In the assign(10,7,3) case, the balance is typically better with
find.BIB(7,10,3):
apply(replicate(10,table(assign(10,7,3))),2,range)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]322333233 3
[2,]555555555 5
> apply(replicate(10,table(find.BIB(7,10,3))),2,range)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]444444444 4
[2,]555555555 5
>
You will pay a price for find.BIB in CPU time, however.
HTH,
Chuck
__
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.
Re: [R] A combinatorial assignment problem
Thank you, Dan and Bert. Bert - Your approach provides a solution. However, it has the undesired property of referees lumping together (I apologize that I did not state this as a condition). In other words, it does not "mix" the referees in some random fashion. Dan - your approach attempts to have the desired properties, but is not guaranteed to work. Here is a counterexample: > set.seed(1234) > a <- assignment(40,15,3) > table(a) a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 7 12 7 4 10 8 6 8 13 7 7 11 3 7 Notice that the difference between maximum and minimum candidates for referees is 13 - 3 = 10. Of course, I have to increase the # iters to get a better solution, but for large K and R this may not converge at all. Best regards, Ravi From: Ravi Varadhan Sent: Wednesday, April 30, 2014 1:49 PM To: r-help@r-project.org Subject: 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,]345 [2,]357 [3,]567 [4,]356 [5,]167 [6,]127 [7,]145 [8,]367 [9,]245 [10,]457 > 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.
Re: [R] A combinatorial assignment problem
Thanks, Bert.
I have written this simple code, which is crude, but seems to do a decent job.
It works perfectly when M is a factor of R. Otherwise, it gives decent balance
(of course, balance is not guaranteed). I guess it is possible to take the
results, that are somewhat unbalanced and then reshuffle it semi-randomly to
get better balance. Any improvements are appreciated!
assign <- function(K, R, M, iseed=1234) {
assignment <- matrix(NA, K, M)
N <- R %/% M
Nrem <- R %% M
iseq <- seq(1,K,N)
for (i in iseq){
size <- ifelse(K-i >= N, R-Nrem, M*(K-i+1))
sel <- sample(1:R, size=size, replace=FALSE)
end <- min((i+N-1),K)
assignment[i:end, ] <- sel
}
assignment
}
sol <- assign(40,16,3)
table(sol)
Thanks,
Ravi
-Original Message-
From: Bert Gunter [mailto:gunter.ber...@gene.com]
Sent: Thursday, May 01, 2014 10:46 AM
To: Ravi Varadhan
Cc: r-help@r-project.org; djnordl...@frontier.com
Subject: Re: A combinatorial assignment problem
Ravi:
You cannot simultaneously have balance and guarantee random mixing.
That is, you would need to specify precisely what you mean by balance and
random mixing in this context, as these terms are now subjective and undefined.
You could, of course, randomize the initial assignment of referees to positions
and note also that some mixing of referee groups would occur if m does not
divide r evenly. More explicitly, note that a very fast way to generate the
groups I described is:
rmk <- function(nrefs,size,ncands){
n <- ncands * size
matrix(rep(seq_len(nrefs), n %/% nrefs +1)[seq_len(n)],nrow=
ncands,byrow=TRUE)
}
## corner case checks and adjustments need to be made to this, of course.
> rmk(7,3,10)
[,1] [,2] [,3]
[1,]123
[2,]456
[3,]712
[4,]345
[5,]671
[6,]234
[7,]567
[8,]123
[9,]456
[10,]712
You could then modify this by randomly reordering the referees every time a
complete cycle of the groupings occurred, i.e. after each
nrefs/gcd(nrefs,size) candidates = rows. This would give variable groups and
even assignment. This algorithm could be further fiddled with by choosing nrefs
and size to assure they are relatively prime and then adding and removing
further refs randomly during the cycling.
etc.
Cheers,
Bert
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 Thu, May 1, 2014 at 6:09 AM, Ravi Varadhan wrote:
> Thank you, Dan and Bert.
>
>
>
> Bert – Your approach provides a solution. However, it has the
> undesired property of referees lumping together (I apologize that I
> did not state this as a condition). In other words, it does not "mix"
> the referees in some random fashion.
>
>
>
> Dan – your approach attempts to have the desired properties, but is
> not guaranteed to work. Here is a counterexample:
>
>
>
>> set.seed(1234)
>
>> a <- assignment(40,15,3)
>
>> table(a)
>
> a
>
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
>
> 10 7 12 7 4 10 8 6 8 13 7 7 11 3 7
>
>
>
> Notice that the difference between maximum and minimum candidates for
> referees is 13 – 3 = 10. Of course, I have to increase the # iters to
> get a better solution, but for large K and R this may not converge at all.
>
>
>
> Best regards,
>
> Ravi
>
>
>
> From: Ravi Varadhan
> Sent: Wednesday, April 30, 2014 1:49 PM
> To: r-help@r-project.org
> Subject: 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,]345
>
> [2,]357
>
> [3,]567
>
> [4,]356
>
> [5,]167
>
> [6,]127
>
> [7,]145
>
> [8,]367
>
> [9,]245
>
> [10,]457
>
>>
>
>
>
> Here each row stands for a candidate and the column stands for the
> referees who review that candidate.
>
>
>
> Of course, there a
Re: [R] A combinatorial assignment problem
Ravi Varadhan jhu.edu> writes: > > 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,]345 > [2,]357 > [3,]567 > [4,]356 > [5,]167 > [6,]127 > [7,]145 > [8,]367 > [9,]245 > [10,]457 > > > Isn't this the problem of constructing a balanced incomplete block design? The problem and an R package to handle it are described here: http://www.r-bloggers.com/generating-balanced-incomplete-block-designs-bibd/ As noted there, you cannot always get balance. A Google Scholar search on "balanced incomplete block design" will pop up many classical works on this problem. Maybe try the ExperimentalDesigns Task view. HTH, Chuck __ 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.
Re: [R] A combinatorial assignment problem
Ravi:
You cannot simultaneously have balance and guarantee random mixing.
That is, you would need to specify precisely what you mean by balance
and random mixing in this context, as these terms are now subjective
and undefined.
You could, of course, randomize the initial assignment of referees to
positions and note also that some mixing of referee groups would occur
if m does not divide r evenly. More explicitly, note that a very fast
way to generate the groups I described is:
rmk <- function(nrefs,size,ncands){
n <- ncands * size
matrix(rep(seq_len(nrefs), n %/% nrefs +1)[seq_len(n)],nrow=
ncands,byrow=TRUE)
}
## corner case checks and adjustments need to be made to this, of course.
> rmk(7,3,10)
[,1] [,2] [,3]
[1,]123
[2,]456
[3,]712
[4,]345
[5,]671
[6,]234
[7,]567
[8,]123
[9,]456
[10,]712
You could then modify this by randomly reordering the referees every
time a complete cycle of the groupings occurred, i.e. after each
nrefs/gcd(nrefs,size) candidates = rows. This would give variable
groups and even assignment. This algorithm could be further fiddled
with by choosing nrefs and size to assure they are relatively prime
and then adding and removing further refs randomly during the cycling.
etc.
Cheers,
Bert
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 Thu, May 1, 2014 at 6:09 AM, Ravi Varadhan wrote:
> Thank you, Dan and Bert.
>
>
>
> Bert – Your approach provides a solution. However, it has the undesired
> property of referees lumping together (I apologize that I did not state this
> as a condition). In other words, it does not "mix" the referees in some
> random fashion.
>
>
>
> Dan – your approach attempts to have the desired properties, but is not
> guaranteed to work. Here is a counterexample:
>
>
>
>> set.seed(1234)
>
>> a <- assignment(40,15,3)
>
>> table(a)
>
> a
>
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
>
> 10 7 12 7 4 10 8 6 8 13 7 7 11 3 7
>
>
>
> Notice that the difference between maximum and minimum candidates for
> referees is 13 – 3 = 10. Of course, I have to increase the # iters to get a
> better solution, but for large K and R this may not converge at all.
>
>
>
> Best regards,
>
> Ravi
>
>
>
> From: Ravi Varadhan
> Sent: Wednesday, April 30, 2014 1:49 PM
> To: r-help@r-project.org
> Subject: 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,]345
>
> [2,]357
>
> [3,]567
>
> [4,]356
>
> [5,]167
>
> [6,]127
>
> [7,]145
>
> [8,]367
>
> [9,]245
>
> [10,]457
>
>>
>
>
>
> 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
>
>
__
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.
Re: [R] A combinatorial assignment problem
I had trouble with my email and it went before it should. Here's the
solution I meant to send:
Arrange the r referees in a circle.
start <- 0
Replicate k times{
end <- (start + m-1)%% r
output: c(start,end) +1
start <- (end+1)%% r
}
The start and end pairs give the subsets of referees around the
circle. The distributes the referees to the candidates as evenly as
possible. I leave it to you to translate this into code. It should be
very fast as no combinatorics are required.
-- Bert
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 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,]345
>> [2,]357
>> [3,]567
>> [4,]356
>> [5,]167
>> [6,]127
>> [7,]145
>> [8,]367
>> [9,]245
>> [10,]457
>>>
>>
>> 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.
Re: [R] A combinatorial assignment problem
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 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,]345
> [2,]357
> [3,]567
> [4,]356
> [5,]167
> [6,]127
> [7,]145
> [8,]367
> [9,]245
> [10,]457
>>
>
> 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.
Re: [R] A combinatorial assignment problem
> -Original Message-
> From: r-help-boun...@r-project.org [mailto:r-help-boun...@r-project.org]
> On Behalf Of Daniel Nordlund
> Sent: Thursday, May 01, 2014 1:10 AM
> To: r-help@r-project.org
> Subject: Re: [R] A combinatorial assignment problem
>
> > -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,]345
> > [2,]357
> > [3,]567
> > [4,]356
> > [5,]167
> > [6,]127
> > [7,]145
> > [8,]367
> > [9,]245
> > [10,]457
> > >
> >
> > 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
>
>
I apologize for the noise. I made some last second edits and cut and pasted
the wrong code in the first email. Obviously, you would want to add some error
checking to the code to trap incompatible parameter specification.
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((max(tbl)-min(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.
Re: [R] A combinatorial assignment problem
> -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,]345
> [2,]357
> [3,]567
> [4,]356
> [5,]167
> [6,]127
> [7,]145
> [8,]367
> [9,]245
> [10,]457
> >
>
> 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.
