Простой алгоритм (РЕДАКТИРОВАТЬ 2)
Из комментариев ниже: у вас есть один отборочный турнир.Вы должны выбрать места игроков в турнирной таблице.Если вы посмотрите на свою сетку, вы увидите: игроков, но также и пары игроков (игроков, которые играют матч 1 против друг друга), пары пар игроков (победитель пары 1 против победителя пары 2 в матче 2),и т. д.
Идея
- Сортировка учащихся по школам, по тем школам, в которых больше учеников, до школ с меньшим количеством учеников.например, ABBBBCC -> BBBBCC A.
- Распределите учащихся по двум группам A и B, как в карточной игре: 1-й студент в A, 2-й студент в B, 3-й студент в A, 4-й студент в B,...
- Продолжите с группами A и B.
У вас есть рекурсия: позиция игрока на уровне k-1 (k = n-1 до 0)((pos at level k) % 2) * 2^k + (pos at level k) // 2 (каждое четное число идет влево, каждое нечетное число идет вправо)
Код Python
Сортировать массив по количеству школ:
assert 2**math.log2(len(players)) == len(players) # n is the number of rounds
c = collections.Counter([p.school for p in players])
players_sorted_by_school_count = sorted(players, key=lambda p:-c[p.school])
НайтиКонечная позиция каждого игрока:
players_sorted_for_tournament = [-1] * 2**n
for j, player in enumerate(players_sorted_by_school_count):
pos = 0
for e in range(n-1,-1,-1):
if j % 2 == 1:
pos += 2**e # to the right
j = j // 2
players_sorted_for_tournament[pos] = player
Это должно дать достаточно разнородные группы, но я не уверен, является ли это оптимальным или нет.Жду комментариев.
Первая версия: как собрать пары из учеников разных школ
Просто сложите учеников из одной школы в стопку.У вас столько стека, сколько школ.Теперь сортируйте свои стеки по количеству студентов.В вашем первом примере {A A A B B C} вы получите:
A
A B
A B C
Теперь возьмите два верхних элемента из двух первых стеков.Размеры стеков изменились: при необходимости измените порядок стеков и продолжайте.Когда у вас есть только один стек, делайте пары из этого стека.
Идея состоит в том, чтобы как можно больше "стеков-стеков" было как можно дольше: вы экономите ученикам небольшие стеки, пока у вас нет выборано взять их.
Шаги со вторым примером, {A A A A B C}:
A
A
A
A B C => output A, B
A
A
A C => output A, C
A
A => output A A
Это проблема соответствия (РЕДАКТИРОВАТЬ 1)
Я подробно остановлюсь на комментариях ниже.У вас есть один отборочный турнир.Вы должны выбрать места игроков в турнирной таблице.Если вы посмотрите на свою сетку, вы увидите: игроков, но также и пары игроков (игроков, которые играют матч 1 против друг друга), пары пар игроков (победитель пары 1 против победителя пары 2 в матче 2),и т. д.
Ваше решение - начать с набора всех игроков и разбить его на два набора, максимально возможных.«Разнообразный» означает здесь: максимальное количество разных школ.Для этого вы проверяете все возможные комбинации элементов, которые разбивают набор на два подмножества равного размера.Затем вы выполняете ту же самую рекурсивную операцию с этими сетами, пока не дойдете до уровня игрока.
Другая идея - начать с игроков и попытаться создать пары с другими игроками из другой школы.Давайте определим расстояние: 1, если два игрока в одной школе, 0, если они в другой школе.Вы хотите создать пары с минимальным глобальным расстоянием.
Это расстояние может быть обобщено для пар игроков: возьмите число общих школ.То есть: ABAB -> 2 (A & B), ABAC -> 1 (A), ABCD -> 0. Вы можете представить расстояние между двумя сетами (игроки, пары, пары пар, ...): числообщих школ.Теперь вы можете видеть это как график, вершинами которого являются множества (игроки, пары, пары пар, ...) и ребра которого соединяют каждую пару вершин с весом, который является расстоянием, определенным выше.Вы ищете идеальное соответствие (все вершины совпадают) с минимальным весом.
Алгоритм Блосса или некоторые его варианты, кажется, соответствуют вашим потребностям, но, вероятно, это излишне, есликоличество игроков ограничено.