Как создать равномерное распределение по нескольким наборам?

Question

Это для проекта хобби и будет реализовано с Python, но это не очень важно. Я в основном ищу хороший алгоритм.

Я хочу провести гоночное мероприятие с 2-30 драйверами (num_drivers). Мероприятие имеет от 2 до 12 гонок (num_races), и я хочу, чтобы каждый водитель имел шанс по своему усмотрению в начале, используя несколько случайное позиционирование. Проблема в том, какие начальные позиции я назначаю каждому драйверу для каждой гонки?

Пример: для события с num_races=3 и num_drivers=4 (названный «А» до «D») очень хорошая установка будет

Race 1: A B C D 
Race 2: C D B A 
Race 3: D B A C 

шест позиция будет иметь значение 1, вторая позиция 2 и т. Д. Поэтому эта установка дает вполне равные значения для каждого драйвера:

A: 1+4+3 = 8 
B: 2+3+2 = 7 
C: 3+1+4 = 8 
D: 4+2+1 = 7 

В конце концов сумма позиций каждого водителя в идеале должны быть такими же, как и для любого другого водителя. Что было бы хорошим универсальным алгоритмом (в псевдокоде) для моей проблемы, когда количество драйверов и количество гонок может варьироваться? Есть ли даже алгоритм где-то посмотреть?

Answer 1

Я нашел красиво работающий PHP-скрипт на github, который решает проблему для меня. Итак, если кто-то заинтересован в ответе на мою проблему: https://github.com/FriendlyBaron/GridCreator

Answer 2

Я хотел бы начать с:

Race 1: A B C D 
Race 2: A B C D 
Race 3: A B C D 

и вращать каждую строку на число гонки,

Race 1: A B C D 
Race 2: D A B C 
Race 3: C D A B 

Отдает:

A = 1 + 2 + 3 = 6 
B = 2 + 3 + 4 = 8 
C = 3 + 4 + 1 = 8 
D = 4 + 1 + 2 = 7 

Что достойного распределения, а также о так же хорошо, как вы собираетесь (я думаю!) с этим размером пула.

Случайный будет работать, если у вас много драйверов.

Вы всегда можете это сделать, найти свои минимумы и максимумы и исправить замкнутый контур. Итак, в приведенном выше примере я хотел бы отметить, что A - < < B и C, поэтому я могу поменять верхний уровень C (4) на следующий высокий A (3) и завершить с 7,8,7,7.

Тривиально для этого размера набора, но, вероятно, не столько с большими сетками.

Если у вас было 4 гонки, вы получите DC (оценка 10 для каждого водителя), но я сомневаюсь, что вы хотите иметь 64 гонки для 64 драйверов (например).

Другим подходом было бы определить балл, который вы хотите для каждого драйвера, а затем работать назад для создания сетки. Используйте взвешенную очередь - наивысший приоритет, предоставляемый водителю с наименьшим счетом, - и, при заполнении сетки, просто хватайте водителя с наименьшей оценкой, чтобы поставить в текущее положение. Это немного похоже на проблему упаковки бункера, но должно работать достаточно хорошо.