Fair 2-combinations
Posted
by
Tometzky
on Programmers
See other posts from Programmers
or by Tometzky
Published on 2013-07-03T13:58:49Z
Indexed on
2013/07/03
17:18 UTC
Read the original article
Hit count: 321
algorithms
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?
© Programmers or respective owner