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: 293

Filed under:

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

Related posts about algorithms