Жеребьевка Лиги Чемпионов в формате 2024/2025

[lineker]

Для тех, кто не знаком, объясню. Начиная с сезона 2024/2025 36 команд, пробившихся в общую сетку, делятся согласно текущего рейтинга на 4 корзины, по 9 команд в каждой. Каждая команда на данной стадии играет 8 матчей, 4 дома и 4 на выезде с командами из каждой корзины, включая свою собственную. То есть, 4 игры дома с соперниками из разных корзин, и 4 в гостях, также из разных корзин, но чтобы все соперники для кажодй команды были разные. Также впервые в жеребьевке участвовала компьютерная программа. Первый шарик для команды выбирал ДжиДжи Буффон из реальной корзины, а для определения соперников КриРу громко стучал по большой кнопке, очевидно инициализируя таким образом компьютерный рендомайзер, после чего для каждой команды высыпались все его соперники, домашние и выездные.

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

Теперь вопрос. Как привязать уже известные пары соперников к конкретным раундам? Какой алгоритм?

[Гость]

Чтобы привязать уже известные пары команд к конкретным раундам, можно использовать алгоритм, который обеспечивает:

Равномерное распределение домашних и выездных матчей: каждая команда играет ровно по 4 матча дома и на выезде.
Минимизацию накладок: чтобы в одном раунде не было слишком большого количества домашних или выездных матчей для одной и той же команды.
Разные соперники в каждом раунде: чтобы не повторять встречи с теми же командами.

Алгоритм привязки пар к раундам

Создать пустой календарь на 8 раундов, куда мы будем размещать матчи.

Разбить пары матчей на группы для каждого раунда:
Каждую команду можно заранее пометить, с кем она играет дома и с кем на выезде.
Проверить, чтобы каждая команда в каждом раунде имела один матч (либо домашний, либо выездной).

Обеспечить чередование матчей дома и на выезде: каждая команда должна по возможности чередовать домашние и выездные матчи.

Итеративное размещение матчей:
Начинаем с первого раунда и размещаем пары, проверяя, чтобы не было совпадений для команд (например, чтобы они не играли дважды подряд дома или дважды подряд на выезде).
Если столкнемся с конфликтом, можно попытаться переставить пары между раундами.

Использовать жадный алгоритм для оптимизации: пройтись по всем парам и найти оптимальное место для каждой пары в расписании, начиная с первого раунда.



Это можно реализовать на Python, используя жадный алгоритм с перестановкой для устранения конфликтов