具有相同计数的随机配对

问题描述：

我正在研究一些将允许评估者评估某些内容的代码（含糊不清，对吧？）。在评估可能发生之前，需要对提交的项目进行随机抽样。这部分相当简单。具有相同计数的随机配对

弄脏我的部分是要求每个项目都需要由两个不同的评估者进行评估，并且我们希望每个评估者执行的最终评估数量尽可能均匀分布。例如：如果我有10个项目，那么应该出来20个评估（每个项目2个评估）。评估人员共有20位评估人员，其中4位评估者评估结果为5位评估人员。很显然，这些数字并不会总是这么干净（11个项目仍然会出现在每位评估员5位，其余两位在每个人都平衡后都会被分配到最高位）。

只是在这里寻找一些算法帮助。最接近我可以得到更多的钟形曲线比我希望的。

答

对我来说，看起来你需要在M个评估者之间分配N个项目的2N个评估，这样每个评估者将获得相同的份额或尽可能接近他们的份额。

有身份：

2N = ceil(2N/M) + ceil((2N-1)/M) + ... + ceil((2N-M+1)/M)

可用于这一目的。 ceil这里是最近的非较小整数为：ceil（2.3）= 3，小区（4）= 4

对于你例的11个项目，你将有22 = 5 + 5 + 4 + 4 + 4

它是如何工作的？我会向您推荐“具体数学”的克努特，Patashnik &格雷厄姆，第3章，第4部分的解释:)

我编写Anttis'的方针和‘混凝土数学’中所描述的：

public static void main(String[] args) { 
    wayOne(5, 7); 
    System.out.println("======"); 
    wayTwo(5, 7); 
} 

private static void wayOne(int assessors, int items) { 
    Integer assessments[][] = new Integer[2][items]; 
    int assessor = 0; 
    for (int pass = 0; pass < 2; pass++) { 
     for (int item = 0; item < items; item++) { 
      while (assessments[pass][item] != null) 
       assessor = (assessor + 1) % assessors; 
      assessments[pass][item] = assessor; 
      assessor = (assessor + 1) % assessors; 
     } 
    } 

    for (int pass = 0; pass < assessments.length; pass++) { 
     for (int item = 0; item < assessments[pass].length; item++) 
      System.out.println("Pass " + pass + " item " + item + " is assessed by " + assessments[pass][item]); 
    } 
} 


private static void wayTwo(int assessors, int items) { 
    Integer distribution[][] = new Integer[2][items]; 
    int assessments = 2 * items; 
    int step = 0, prevBatch = 0; 
    while (assessments > 0) { 
     int batch = (int) Math.ceil((2.0 * items - step)/assessors); 
     assessments -= batch; 
     for (int i = prevBatch; i < batch + prevBatch; i++) { 
      distribution[i/items][i % items] = i % assessors; 
     } 
     prevBatch += batch; 
     step++; 
    } 

    for (int pass = 0; pass < distribution.length; pass++) { 
     for (int item = 0; item < distribution[pass].length; item++) 
      System.out.println("Pass " + pass + " item " + item + " is assessed by " + distribution[pass][item]); 
    } 
}

~~如果我是正确的，第二种方法将提供更多期望的输出。例如，尝试7个项目和5个评估者。或者11个项目和4个评估员。~~

UPDATE当我修正了Antti指出的错误后，两个例程给出了相同的结果。

是的，但是在我的算法实现中存在一个错误。您重新设置评估人指数，导致完全不同的算法和绝对较差的性能！赋值评估器= 0在我的代码中遍历循环之外！ :)它属于迭代之前通过。难怪你会得到不好的结果。 – 2011-04-19 02:44:49

@antti谢谢你指出这一点！我已经更新了答案。 – 2011-04-19 05:32:00

算法:)中仍然存在一个错误:) while（assess [pass] [item]！= null）'''''''''''''''''''''' – 2011-04-19 15:54:39

答

这并不困难。假设您有一个访问器和I项。只要运行下面的循环（一切都是从零开始的索引）：

a = 0 
for 0 <= r < 2: 
    for 0 <= i < I: 
    while (assessor a is already assessing item i): 
     a = (a + 1) mod A 
    assessor a will assess item i on round r 
    a = (a + 1) mod A

在循环方式这只会分配评估，但会跳过那些情况下，同样的评估者会两次评估相同的项目。

具有相同计数的随机配对

相关推荐