Случайные пары с равным количеством

Question

Я работаю над кодом, который позволит оценщикам что-то оценивать (расплывчато, верно?). Перед проведением оценки необходимо выбрать случайную выборку из представленных предметов. Эта часть довольно проста.

Часть, которая меня обескураживает, - это требование о том, что каждый элемент должен оцениваться двумя разными оценщиками, и что мы хотим, чтобы окончательное количество оценок, которые выполняет каждый оценщик, было как можно более равномерно распределено.

Пример: если у меня есть 10 пунктов, то должно получиться 20 оценок (2 оценки на элемент). 20 оценок, разделенных на 4 оценщика, дают 5 оценок на каждого оценщика. Очевидно, что цифры не всегда будут такими чистыми (11 пунктов все равно получится по 5 на каждого эксперта, а оставшиеся два будут назначены на первое место после того, как все выровняются).

Просто ищу некоторую алгоритмическую помощь здесь. Самое близкое, что я могу получить, это то, что я получаю больше кривой кривой, чем мне бы хотелось.

Answer 1

Это не сложно.Допустим, у вас есть аксессуары A и 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

Это просто распределит оценщиков круговым методом, но пропустит те случаи, когда один и тот же оценщик будет оценивать один и тот же элемент.в два раза.

Answer 2

Мне кажется, что вам нужно распределить 2N оценок по N пунктам между M оценщиками, чтобы каждый оценщик получил равную свою долю или максимально приблизился к ней.

Есть личность:

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

, который можно использовать для этой цели. ceil вот ближайшее не меньшее целое число: ceil (2.3) = 3, ceil (4) = 4

Для вас пример из 11 предметов у вас будет 22 = 5 + 5 + 4 + 4 + 4.

Как это работает? Я отошлю вас к «Конкретной математике» Кнута, Паташника и Грэма, глава 3, часть 4 для объяснения:)

Я закодировал подход Анттиса и тот, который описан в «Конкретной математике»:

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 оценщика.

ОБНОВЛЕНИЕ После того, как я исправил ошибку, указанную Antti, две процедуры дают одинаковые результаты.