I need to fairly assign 2 experts from x experts (x is rather small – less than 50) for every n applications, so that:
- each expert has the same number of applications (+-1);
- each pair of experts (2-combination of
x) has the same number of applications (+-1);
It is simple to generate all 2-combinations:
for (i=0; i<n; i++) {
for (j=i+1; j<n; j++) {
combinations.append(tuple(i,j));
}
}
But to assign experts fairly I need to assign a combination to an application i correct order, for example:
experts: 0 1 2 3 4
fair combinations:
counts
01234
01 11000
23 11110
04 21111
12 22211
34 22222
02 32322
13 33332
14 34333
03 44343
24 44444
I’m unable to come up with a good algorithm for this (the best I came up with is rather complicated and with O(x4) complexity). Could you help me?
You just need to cycle the possible pairings in an order that guarantees that the usage counts for each person differ by no more than one. This is the same problem as generating pairings for a round robin tournament. If you have an even number of people, one simple technique for generating pairings is to arrange them in two rows. Hold the top-left person fixed, and rotate the rest.
1) a b c
f e d
2) a c d
b f e
3) a d e
c b f
4) a e f
d c b
5) a f b
e d c
In each cycle, “a” is fixed and the other people rotate. Read pairings vertically. So you would cycle through pairings as follows:
af be cd ab cf de ac bd ef ...
With an odd number of people, leave the stationary box empty and ignore that column.
2
Here’s some musings and ideas, although no code:
Given x experts, n applications and each expert has the same number of applications (+-1), you can trivially derive that each expert will average (n/x) applications. If this is a fraction, some of the experts will round up and the others will round down.
So define a = floor(n/x); b = a+1; These are your only allowed values for each expert’s number of applications. Additionally, you know that all the a and b combined have to sum to n.
When choosing tuples, you simply pair each a expert with a b expert until you run out of one or the other, then pair up the rest.