Алгоритм группировки - турнир

#algorithm #performance #grouping

#алгоритм #Производительность #группировка

Вопрос:

Ищу алгоритм или код, если у кого-то хватит щедрости сделать следующее. Мне нужно принять входные данные для нескольких игроков. Количество игроков всегда будет в 4 раза больше. Я хочу сгруппировать отдельных игроков в группы по 4 человека с наименьшим количеством повторений. Первоначальное размещение тривиально:

  1   2   3   4   Table 1
 5   6   7   8   Table 2
 9  10  11  12   Table 3
13  14  15  16   Table 4
17  18  19  20   Table 5
21  22  23  24   Table 6

Итак, игроки 1-4 «видели» друг друга один раз. Каждый играет в свою игру, а затем игроки перетасовываются. На следующем проходе (и последующих проходах) Я хочу переставить игроков так, чтобы у них было наименьшее количество совпадений. В принципе, я хочу, чтобы игрок не видел повторяющееся лицо как можно дольше, и как только это станет невозможным, я хочу максимально свести его к минимуму.

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

Для наглядности никто не выбывает, они просто перетасовываются каждый раз.

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

2. Я использую C , но меня не особенно волнует, на каком языке он написан. Меня больше интересует мыслительный процесс / псевдокод. Общий подход, который я использовал изначально, заключался в том, чтобы перебрать каждого «игрока» и рассадить их с людьми, у которых было наименьшее количество случаев сидеть с ними ранее. Но я чувствовал, что это сильно повлияло на игроков с более низким индексом. Я могу использовать любые предложения Java / C / C / .NET / PHP.

3. В идеале я хотел бы иметь переменное количество раундов… Я бы предположил, что это не сильно повлияет на правильное решение. В реальном примере у меня 28 игроков и 6 раундов. Оба из которых могут меняться в дальнейшем.

4. @JamesB41, у меня почти идентичная проблема. с переменным количеством игроков и переменным количеством раундов. Вы когда-нибудь находили решение? Спасибо!

5. В итоге мне действительно повезло, и мне понадобилось практическое решение только для нескольких вариантов, все из которых были найдены в этой таблице: cs.brown.edu /~sello/golf.html

Ответ №1:

По сути, это проблема социального игрока в гольф. В литературе по комбинаторной оптимизации существует множество алгоритмов.