Выбор честных команд - и математика, чтобы доказать это

Question

Применение: похоже на сбор игровых площадок команд.

Я должен разделить коллекцию из n последовательно ранжированных элементов на две команды из n / 2.Команды должны быть как можно более «четными».Подумайте о «даже» в терминах игровых команд, как описано выше.Рейтинги указывают на относительный уровень «мастерства» или значения.Элемент № 1 стоит 1 «балл», элемент № 2 стоит 2 и т. Д. Никаких других ограничений.

Так что, если бы у меня была коллекция [1,2,3,4], мне понадобилось бы две командыиз двух элементов.Возможные варианты:

[1,2] & [3,4]

[1,3] & [2,4]

[1,4] & [2,3]

(Порядок не важен.)

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

[1,2,3,4,13,14,15,16] & [5, 6,7,8,9,10,11,12]

Я могу использовать грубую силу, чтобы оценить все возможные варианты решения для моей проблемной области.

Есть ли какой-то математический / статистический подход, который я могу использовать для проверки "ровности" двух команд?

Спасибо!

Answer 1

Ваш второй, более длинный пример, не кажется мне неровным (или несправедливым). Фактически, это согласуется с тем, что, как вам кажется, является предпочтительным ответом для первого примера.

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

Вы можете, например, сравнить каждый элемент из двух наборов по очереди, например, a1 vs b1, a2 vs b2, ... и считать наборы даже достаточными, если число случаев, когда a лучше, чем b, примерно равно числу случаев. где б лучше, чем а.

Но для вашего приложения я не думаю, что вам будет лучше, чем использовать алгоритм игровой площадки, каждый руководитель группы выбирает лучшего не выбранного игрока и по очереди выбирает альтернативного. Зачем тебе что-то более сложное?

Answer 2

Не думаю, что для определения ответа достаточно информации.

Что на самом деле означает, что кто-то должен быть № 1 против № 2?Они на 50% лучше, или на 10% лучше, или на 1% лучше?Насколько лучше № 1 против № 5?Это действительно алгоритм для назначения значения, которое должно быть точным, и алгоритм распределения должен отражать это должным образом.

Например, как я уже сказал, если у вас есть Коби Брайант, смешанный с группой старших классов средней школыдети баскетбола, какими будут относительные ценности?Потому что в баскетболе Коби Брайант мог в одиночку победить всех школьников.Значит, его ранг будет # 1, а остальные дети будут # 1000 +?

Также вы должны предположить, что при определении значения учитывается размер команды.Команде нужны только 2 игрока?Или нужно 10?В последнем случае, во втором примере, вторая команда выглядит нормально, потому что лучшие 4 игрока будут играть с 6 гораздо худшими игроками, что может повлиять на успех.

Если все, что вы делаете, это распределение ценностей,и если понятие «справедливости» встроено в систему ценностей, то средние значения кажутся справедливым способом распределения игроков.

Answer 3

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

[1] & [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

составляется против большой команды. Это было бы, например, для шахматных команд, если разница между [1] и [2] была большой.

Даже матч, который вы назвали «нечестным»:

[1,2,3,4,13,14,15,16] & [5,6,7,8,9,10,11,12] 

Может быть абсолютно честным в такой игре, как бейсбол. В конце концов, игрокам 13-16 все еще нужно бить!

---

Так что, наверное, самое справедливое, что нужно сделать, это просто выбрать команды случайным образом. Это также позволило бы избежать любой формы "игровой" системы (как это делали мои друзья и я на уроках физкультуры в средней школе :))

Answer 4

Вам нужен итеративный подход к ранжированию с автоматическим выбором, чтобы производить команды с одинаковым рейтингом на каждой итерации. Это работает, даже когда состав участников меняется в некоторой степени с течением времени. Я создал инструмент, чтобы сделать это для моей группы из 5 человек, а затем открыл его для всех желающих, если вы выбрали Google для "Fair Team Picker"

Answer 5

Разве команды не равны, если каждый «раунд» выбора просто делается в обратном порядке предыдущего раунда?Если есть 10 игроков с талантом 1-10, и мы создаем 5 команд (по 2 игрока в каждой), то в первом раунде первый выбор, очевидно, выберет лучшего игрока (уровень таланта 10).Тогда следующий выбор будет 9, и так далее.Пятый пик получит игру с уровнем таланта 6. Во втором раунде порядок выбора меняется на противоположный, поэтому команда, которая только что получила уровень таланта 6, выберет уровень таланта 5 (самый верхний слева) и так далее до капитана.кто выбрал первый в 1-м раунде, получит последнего игрока (уровень таланта 1).Таким образом, у каждой команды есть уровень таланта 11, у одной команды 10 и 1, у другой 9 и 2, и так далее.Это будет работать для такого количества игроков / команд, сколько есть.