Сортировка пар команд с неповторяющимися | Круговой турнир

Question

Я создаю график турнира. Каждая команда должна сыграть ровно 8 игр. Количество команд 2 < < н 36

Для сортировки команд на пары я использую алгоритм Round Robin, чтобы получить таблицу, пример 6 команд:

Тогда я преобразовать его в набор пар:

1 4 
2 3 
3 2 
4 1 
5 6 
6 5 
1 2 
2 1 
3 5 
4 6 
5 3 
6 4 
... 

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

---

Пример с новым алгоритмом:

Answer 1

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

Wikipedia Round-robin Tournament Scheduling Algorithm

Начнем со случая 8 команд. [Т , Т , Т , Т , Т , Т , Т , Т ]

Попробуем смотреть на эту проблему, как так ..

T T T Т
Т Т Т Т

Итак, теперь. Матчи -> [(1,5), (2,6), (3,7), (4,8)].

Повернуть список по часовой стрелке, но сохранить положение T исправлено.

Т Т Т Т
Т Т Т Т

Итак, теперь. Матчи -> [(1,5), (2,6), (3,7), (4,8), (1,6), (5,7), (2,8), (3,4)].

В этом случае должно произойти 7 возможных поворотов до начала дублирования. В традиционном раундовом турнире есть (n/2)*(n-1), где n - количество команд. Это должно работать независимо от количества задействованных команд. [Если вы столкнулись с n%2 == 1, поставьте X, чтобы сделать набор ровным и продолжить, как обычно; одна команда будет сидеть в одном матче].

Если вам необходимо убедиться, что каждая команда должна играть 8 игр, сделать точно 8 поворотов, когда число команд даже.

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

Редактировать.

Начнем с случая с 3 командами. [T , T , T ]

Давайте попробуем взглянуть на эту проблему, как так ..

T T
T X

Итак, сейчас. Матчи -> [(1,3), (2, X)].

Повернуть список по часовой стрелке, но сохранить положение T исправлено.

Т Т
Х   Т

Итак, теперь. Матчи -> [(1,3), (2,X), (1, X), (3,2)].

Следующий корпус, матчи -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X, 3)].

Следующий случай, матчи -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2, X)].

....

Матчи -> [(1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3), (1,3), (2,X), (1,X), (3,2), (1,2), (X,3)].

1 -> [3,X,2, 3,X,2, 3,X,2, 3,X,2]
2 -> [X,3,1, X,3,1, X,3,1, X,3,1]
3 -> [1,2,X, 1,2,X, 1,2,X, 1,2,X]

Если вы заметили шаблон, вы увидите, что в этих условиях невозможно обеспечить, чтобы команды не играли в игры назад к игре. Он потребовал 12 поворотов, чтобы каждая команда сыграла 8 игр. Я пытаюсь придумать формулу и соответственно обновить эту должность.