Руководитель направления систем бизнес-аналитики BIA Technologies Станислав Воронин рассказывает, как математическая модель решает кому, когда и с кем играть в следующем сезоне, и размышляет о дивном новом будущем спорта.
Математическая оптимизация расписаний
«Ну кто додумался поставить в сетку выездную встречу с «Ювентусом» на этот вторник?! Ребята только отыграли сложнейший матч на домашнем поле!» — восклицаете вы в гневе. И напрасно: расписание составил не человек, а компьютер, и сделал он это на основе сложнейшей математической модели. Как? Сейчас расскажу.
Разумеется, речь пойдёт не о любительских соревнованиях между студенческими командами, а о составлении расписаний для высших спортивных лиг (Российская премьер-лига, итальянская Серия А, НБА, КХЛ и т.д.). Сетка для матчей такого уровня должна учитывать столько ограничений, что составить расписание вручную просто невозможно, поэтому лиги поручают это ответственное дело компьютеру.
Помимо специфических правил в разных типах турниров и видах спорта, существует ряд универсальных требований, единый для всех. Вот ключевые вводные:
1. Предпочтительно, чтобы матчи проводились по выходным или в будни по вечерам (так их увидит больше зрителей); самые зрелищные — в телевизионный прайм-тайм.
2. Нежелательно, чтобы в одно и то же время параллельно проходило несколько популярных матчей самых титулованных команд (болельщикам придётся переключаться между телеканалами).
3. Матчи следует равномерно распределять по сезону; между играми у команды должен быть перерыв не менее 48 часов (это время на отдых и подготовку спортсменов).
4. Домашние и выездные матчи должны чередоваться; нельзя проводить все домашние игры скопом в начале сезона (так как играть на родном стадионе традиционно легче, это создаст ложное ощущение превосходства).
5. Необходимо учитывать часовые пояса, джетлаги и время на переезд спортсменов из одного города/страны в другую.
6. Домашняя и выездная игры между двумя соперниками должны быть разнесены как можно дальше в расписании.
7. Необходимо учитывать уровни команд: нельзя, чтобы команда играла несколько матчей подряд с лидерами дивизиона — череда сложных игр вымотает спортсменов и поставит их в невыгодное положение перед соперниками.
8. Желательно не сводить явных фаворитов в первые две недели сезона (это сведёт на нет всю интригу).
9. Нужно учитывать занятость игроков в европейских чемпионатах: команды не любят играть с сильными соперниками прямо перед встречами еврокубков.
10. Сетка должна учитывать доступность стадионов под другие мероприятия.
Как видно по этому списку, составление расписания — это сложная эквилибристика, поиск идеального баланса между возможностями спортсменов, желаниями зрителей и максимальной финансовой выгодой для клубов и телеканалов. Правильно составленное расписание, которое учитывает все вышеуказанные условия, приносит лигам огромный доход от рекламы, трансляций и продажи билетов, поэтому создание соответствующей математической модели для планирования матчей стоит баснословных денег.
При изменении любого из этих правил или добавлении нового необходимо рассчитать, как изменится вся система в целом. Это сродни игре в шахматы: прежде чем передвинуть фигуру, нужно оценить, как изменится расклад на доске и просчитать последствия на несколько ходов вперёд. В итоге проще предоставить решение компьютеру, и математическая оптимизация сама сделает всю работу.
За календарь Российской футбольной премьер-лиги с 2019 года отвечает алгоритм, разработанный НИУ ВШЭ. Если вам интересны детали, в интервью изданию «Спорт-Экспресс» сотрудники лаборатории исследований спорта рассказали о своей методологии и российской специфике. Так, например, нежелательно проводить пять матчей в одном туре в Москве, поскольку это создаст сложности для МВД. Кроме того, в большинстве регионов страны зимой не поиграешь в футбол на открытом поле.
Искусственный интеллект vs. магия спорта
Сейчас всё больше решений в мире спорта принимается искусственным интеллектом на основе большого количества данных. И речь не только о расписании матчей. Камеры и датчики фиксируют каждое движение спортсмена, компьютер анализирует информацию и выдаёт рекомендации. Есть мнение, что в будущем вообще отпадёт необходимость в тренерском штабе: принимать решения о стартовом составе, сажать игроков на скамейку запасных, программировать режим тренировок, составлять рацион и давать тактические советы перед каждой игрой будет искусственный интеллект.
Во многих случаях компьютер действительно может заметить неочевидные взаимосвязи и предложить оптимальное решение. Вот интересный пример: защитник «Арсенала» Эктор Бельерин в начале сезона 2021/2022 перешёл на правах аренды в испанский клуб «Реал Бетис». Чтобы выбрать идеальный для себя вариант (по слухам, среди них были такие тяжеловесы как «Барселона», «Интер» и «ПСЖ») Бельерин обратился за помощью в консалтинговую фирму Analytics FC. Эксперты компании создали математическую модель специально под футболиста.
Алгоритм проанализировал множество факторов и подсказал, что текущая схема 4-3-2-1, которую предпочитает тренер «Реал Бетис», лучше всего сочетается со стилем игры Бельерина. Кроме того, данные показали, что команда нуждается в крайнем защитнике после трансфера Эмерсона, что точно не позволит Бельерину скучать на скамейке запасных. Наконец, игра в испанском клубе должна увеличить шансы футболиста на попадание в национальную сборную Испании к ближайшему Чемпионату мира. Эксперты говорят, что это первый случай в истории, когда игрок принял решение о трансфере при помощи аналитики.
Но есть и обратная сторона медали. Действительно ли мы готовы отдать на откуп ИИ принятие абсолютно всех решений? Дал бы он шанс, скажем, юному Лионелю Месси с его небольшим ростом и проблемным здоровьем, или сходу посчитал бы его бесперспективным форвардом? А хороший тренер — это просто «оптимизатор», который сравнивает статистику сутками напролёт, или харизматичный тактик, психолог и родитель в одном лице? Может ли условного Теда Лассо полностью заменить компьютер?
В 2018 году вышел документальный фильм «В поисках величия», который задавался примерно такими вопросами. Авторы поговорили с такими легендами спорта как Пеле, Уэйн Гретцки и Джерри Райс, и пришли к выводу, что искусственный интеллект лишил бы нас многих «неочевидных» звёзд. Один из примеров, приводимых в фильме, — чемпион мира по боксу Рокки Марчиано. Он был ниже большинства соперников и не обладал большим размахом рук. Но эти «недостатки» помогли ему найти свой собственный подход: он наклонялся ниже и бил в упор на короткой дистанции. Марчиано не проиграл ни одного поединка в своей карьере и считается одним из лучших боксёров в истории.
Тем не менее сейчас спорт движется в направлении всё большей автоматизации в принятии решений. Насколько это рационально — покажет время. Но мне бы всё-таки хотелось, чтобы часть решений осталась за людьми. В конце концов, мы любим спорт за человеческие моменты, красивую игру, командный дух, эпизоды невероятной удачи и «руку Бога». Если оставить выбор за компьютером, спорт перестанет быть искусством. А вы что думаете?
Правильно будет в любом случае, а вручную такое расписание составлять долго. Проще программой.
1. Скачать программу «Футбольные чемпионаты» на её офсайте.
2. Создать файл чемпионата.
3. Зайти в созданный файл.
4. Нажать кнопку: Настройки — Опции — Автодобавление календарных игр
5. Нажать кнопку: Настройки — Опции — В календарных играх случайным образом заполнить туры
Если нужна дата, то указать в пуккте 5 дату первого тура и промежуток дней между турами.
Если между турами разное количество дней — проставить даты вручную.
Для 16-ти команд программа выдаст такой календарь.
1 тур: 1-16, 2-15, 3-14, 4-13, 5-12, 6-11, 7-10, 8-9,
2 тур: 1-2, 10-8, 11-7, 12-6, 13-5, 14-4, 15-3, 16-9,
3 тур: 2-16, 3-1, 4-15, 5-14, 6-13, 7-12, 8-11, 9-10,
4 тур: 1-4, 2-3, 11-9, 12-8, 13-7, 14-6, 15-5, 16-10,
5 тур: 3-16, 4-2, 5-1, 6-15, 7-14, 8-13, 9-12, 10-11,
6 тур: 1-6, 2-5, 3-4, 12-10, 13-9, 14-8, 15-7, 16-11,
7 тур: 4-16, 5-3, 6-2, 7-1, 8-15, 9-14, 10-13, 11-12,
8 тур: 1-8, 2-7, 3-6, 4-5, 13-11, 14-10, 15-9, 16-12,
9 тур: 5-16, 6-4, 7-3, 8-2, 9-1, 10-15, 11-14, 12-13,
10 тур: 1-10, 2-9, 3-8, 4-7, 5-6, 14-12, 15-11, 16-13,
11 тур: 6-16, 7-5, 8-4, 9-3, 10-2, 11-1, 12-15, 13-14,
12 тур: 1-12, 2-11, 3-10, 4-9, 5-8, 6-7, 15-13, 16-14,
13 тур: 7-16, 8-6, 9-5, 10-4, 11-3, 12-2, 13-1, 14-15,
14 тур: 1-14, 2-13, 3-12, 4-11, 5-10, 6-9, 7-8, 16-15,
15 тур: 8-16, 9-7, 10-6, 11-5, 12-4, 13-3, 14-2, 15-1.
Этот пост написан пользователем Sports.ru, начать писать может каждый болельщик (сделать это можно здесь).
Что еще можно будет почерпнуть из деления команд на две
восьмерки? Два сорта, хорошие и недостаточно хорошие. Так вот, при жеребьевке
турнира, можно и даже нужно, в каждом туре иметь главный матч, в котором будут
играть две, из какого то числа лучших команд турнира. Чтобы не было в одном
туре двух матчей уровня «Динамо» — «Спартак» и «Локомотив» — ЦСКА.
Теперь займемся определением, количества этих, элитных
клубов. В одном круге пятнадцать туров, так вот, между двумя лучшими командами
в круге – один матч;
Между тремя – три матча;
Между четырьмя – шесть матчей;
Между пятью – десять матчей;
Между шестью – пятнадцать матчей.
Таким образом, если выделить шесть лучших клубов, то можно
их матчи между собой развести по турам. Остальные же матчи доверить жребию, ну
или кому-то более компетентному.
Что это даст?
Такое распределение позволит Лиге иметь высококачественный
продукт (футбольные матчи), регулярно в течениичемпионата, продукт который
можно будет показывать и зарубежному зрителю.
Клубы среднего уровня будут иметь стимул для попадания в
заветную шестерку, а клубы из нее – стимул остаться в ней. В свою очередь,
появление седьмого, восьмого и далее серьезных клубов в Лиге, вряд-ли пойдет ей
во вред.
Определение участников «большой шестерки».
Сейчас оптимально ее состав выглядит так: ЦСКА, «Зенит»,
«Спартак», «Рубин», «Динамо» и «Локомотив». Пожалуй единственным претендентом
на место в ней является «Анжи», но для этого должен быть и претендент на вылет
из шестерки. В случае, если необходимо выделить не только один матч из тура, а
например два, то кроме «Большой шестерки», можно выделить малую тройку. Матчи
представителей тройки, с первымми шестью командами, сформируют – вторые матчи
тура, это будут по шесть игр, с участием двух из трех клубов плюс игры третьей
команды, с тремя клубами из первой шестерки.
При этом, потребитель может считать первым матчем тура не
«Динамо» — «Локомотив», а «Зенит» — «Крылья Советов», но это уже право
потребителей, в то время как обязанность организатора равномерное распределение
матчей п отурам в зависимости от интереса зрителей.
Если бы это было на самом деле, тогда возникла бы
необходимость, поделить клубы на несколько групп:
Первая тройка, вторая тройка, третья тройка в формате два
плюс один.
Или так – «большая тройка», «большая шестерка», «большая
восьмерка», «большая девятка».
Перва тройка (шесть первых матчей + три вторых): ЦСКА,
«Зенит», «Спартак».
Вторая тройка (шесть + два): «Динамо», «Локомотив», «Рубин».
Третья тройка:
Два клуба (шесть вторых матчей тура): «Анжи» и «Кубань».
Один клуб (три вторых матча тура) – «Краснодар» или
«Ростов».
Попадание в ту или иную группу, можно определить по
популярности клубов, его турнирным успехам, участию в Еврокубках и рейтенгу
трансляций его матчей, да хоть голосованием членов Премьер-лиги. Это ведь не
для раскола ее участников, а для привлечения новых зрителей и поднятия интереса
к турниру.
ЕВРОФУТБОЛ
Англия
КУХНЯ ФУТБОЛА. Помните, у Лескова Левша сигналит с чужбины: «Передайте государю – англичане ружья кирпичом не чистят…» Вот и корреспондент «ССФ», попав на родину футбола, случайно столкнулся с человеком, который вот уже 18 лет успешно составляет календари для английских чемпионатов всех уровней. Естественно, тайна четкости английского календаря была тут же выведана…
Знали бы вы, как пишется календарь и какие нюансы учитываются при его составлении! Я, честно говоря, испытал легкий шок от того, что узнал, и проникся безмерным уважением к человеку, который фактически один справляется с таким титаническим трудом. Но обо всем по порядку…
Приезжаю я в Глостер Плейс, что в самом сердце Лондона, чтобы начать процедуру оформления сезонной аккредитации на матчи английской Премьер-лиги. Волокита бесконечно долгая, да еще с неизвестным финальным результатом – иностранных журналистов аккредитуют неохотно. Хожу по кабинетам, собирая указания о необходимости тех или иных документов, и уже думаю уходить, как что-то толкает меня заглянуть в огромный зал, где несколько мужчин толпятся вокруг необъятного стола и внимательно слушают вооруженного школьной указкой седовласого, но отнюдь не старого господина. Решаюсь зайти…
Кроме указанного стола, в зале нет никакой мебели. На самом столе – огромная карта Великобритании, испещренная неимоверным количеством разноцветных надписей и дат. Седовласого зовут Гленн Томпсон. Он объясняет нескольким представителям разных профессиональных клубов, почему календарь этого сезона составлен именно так, а не иначе. Объясняет легко, со знанием дела. Еще бы, ведь мистер Томпсон пишет календарь английских и шотландских первенств уже 18 лет подряд!
Вскоре «слушатели» попрощались, я представился, и Гленн охотно согласился раскрыть мне секреты календаря. Его должность – ай-ти консультант фирмы «Атос Ориджин» из Эдинбурга (оказывается, календарь всех футбольных лиг попросту заказывается частной фирме!). Видно, что он гордится своим трудом, и не без оснований. На секунду представьте себе объем титанической задачи: 122 профессиональных клуба по всей Великобритании играют больше 5000 матчей для миллионов болельщиков. И всех их надо грамотно развести во времени и пространстве.
УЧЕСТЬ ВСЕ!
– Конечно, я вооружен всевозможными компьютерными программами и приложениями, – говорит Гленн. – Но есть сотни нюансов, которых машине не объяснишь, так что, как бы ни помогала техника, вынужден констатировать, что три четверти календаря приходится писать вручную.
Пытаюсь изобразить невинность и задаю каверзный вопрос:
– Что же в этом сложного?
– Учитывать нужно все. Погоду, нормы и требования безопасности, географию, требования и предпочтения клубов, особенности транспортных сетей, традиции болельщиков, интересы сборной, запросы телевидения, календари ФИФА и УЕФА, регламенты разных кубковых турниров, календарь всяческих культурных мероприятий и многое другое. Словом, это большой пазл, с той лишь разницей, что, ставя один кусок, ты не видишь остальных.
– У нас в России, как ни составь календарь, многие тренеры остаются недовольными…
– Сделать довольными тренеров – не моя работа. Мое дело – обеспечить разумный баланс среди всех 122 клубов, включая их болельщиков и весь обслуживающий персонал в стране. Заметил, что тренеры в Англии начинают жаловаться только тогда, когда начинаются переносы и график игр сильно уплотняется. Но, увы, резервных дней так мало, что иного выбора не остается.
– Каков главный критерий составления календаря?
– Безопасность, естественно! Главное – не допустить хаоса и столпотворения. Вот возьмем Англию. Девяносто два профессиональных клуба четырех лиг разбиваю по парам – в основном по географическому принципу: Ливерпуль – Эвертон, Фулхэм – Челси. Есть пары, которые представляют разные дивизионы, а есть и такие, стадионы которых обслуживает один полицейский департамент – это тоже важный критерий.
– С чего вы начинаете свой труд?
– В апреле рассылаю во все клубы тщательно составленный вопросник с целью детально выяснить пожелания каждого. В этом году было получено 88 просьб, и 72 из них удалось удовлетворить. Затем жду окончания стыковых матчей, в которых определяется, кто и в какой лиге будет играть. Пик моей работы – конец мая. В середине июня календарь уже публикуется.
– Есть ли клуб, который доставляет вам больше хлопот, чем остальные?
– «Вест Хэм», однозначно! Вот смотрите (берет указку в руки): обслуживающий «молотобойцев» полицейский департамент служит также клубам «Лейтон Ориент» и «Дагенхэм энд Редбридж». А клуб «Саутенд» просит развести свои домашние матчи с «Вест Хэмом», ибо они «делят» между собой многих болельщиков. В свою очередь, «Саутенд» в одном полицейском округе с «Колчестером», который нанимает тех же стюардов на домашние матчи, что и «Ипсвич», так что два последних клуба не могут играть дома в один и тот же день. А еще фанаты «Ипсвича» и «Норвича» пользуются одними и теми же поездами, которые отходят с лондонского вокзала «Ливерпуль Стрит». И так далее… Так что, составляя календарь «Вест Хэма», приходится учитывать интересы трети населения Англии. Пару лет назад из-за вынужденного переноса матча «молотобойцев» пришлось также передвинуть 47 других игр!
ПОГОДУ НЕ ПОМЕНЯЕШЬ
– В последнее время матчи в России переносят на вечер из-за жары.
– Да, наслышан о жаре в Центральной России. Правильно делают – погоду, в отличие от расписания поездов, поменять невозможно. Но иногда проще перенести матч на сутки, чем на несколько часов. Впрочем, если клубам удается договориться между собой и получить добро Транспортной полиции, проблем не возникает.
– А пресловутые интересы сборной Англии?
– У нас в стране четыре сборные! Всем не угодишь, но перед составлением календаря я получаю список пожеланий от Футбольной ассоциации и учитываю их по мере возможностей.
– И ваш проект вот так просто утверждают?
– Разумеется, нет! Переделываю первоначальный календарь раз семь, не меньше. Ибо свои коррективы вносят полицейские, транспортники, лондонское метро, Федерация футбольных болельщиков… Интересы последних – святое!
– В чем это выражается?
– Например, в новогодние каникулы движение транспорта ограничено, а болельщики должны попасть на матч. Заметьте, в эти дни играют клубы, расположенные недалеко, но не ближайшие соседи. Дерби в Новый год не играются, потому что и в каникулы, и на дерби трибуны всегда полные, а клубы, особенно мелкие, хотят иметь два гарантированных аншлага вместо одного.
Далее мистер Томпсон рассказывает забавные истории об этих самых мелких клубах. Одни просят никогда не ставить им три подряд выездных матча, ибо три недели подряд без продажи билетов – это прямой риск обанкротиться. Другой клуб попросил перенести домашнюю встречу на выезд, ибо получил выгодный заказ аренды стадиона для свадьбы. Еще один заштатный клуб умолял отодвинуть домашнюю встречу по смешной причине – шеф безопасности взял недельный отпуск. Ежегодная ноттингемская Гусиная ярмарка – весомый повод не проводить футбольные матчи поблизости в те же дни. Рок-концерты – вообще настоящий бич!
– А телевизионщики? У нас в России зачастую они диктуют свои условия.
– ТВ лишь одна из заинтересованных сторон, не более. Решение о переносе времени начала матча все равно принимает премьер-лига с одобрения полиции. Если она скажет «нет», телевизионщикам придется показывать другой матч, и такое уже было.
НЕ ДОВЕРЯЙТЕ КОМПЬЮТЕРАМ!
– Также в России клубы часто договариваются между собой о сроках проведения матча, кажется, не спрашивая своих болельщиков. А еще просят о переносе прямо посередине сезона…
– Не верю, что без учета интересов болельщиков переносятся матчи. Это ведь невыгодно самим клубам. Что касается просьб по ходу сезона, то должны быть весомые причины. Вот у вас вмешалась жара, а у нас в Англии календарь постоянно «портят» дожди. Вынужденно ищем варианты – ведь нельзя портить футбольные поля.
– Сейчас московский «Спартак» проводит серию матчей с остальными сильнейшими командами России, причем в преддверии старта Лиги чемпионов. Это можно считать недочетом составителей календаря?
– Не берусь судить, ибо не знаю внутренней кухни российского футбола, но для «Спартака» это может быть не очень хорошо. Учитываю подобные просьбы клубов английской премьер-лиги. Они поступают каждый год и звучат примерно так: не проводить более двух матчей подряд с грандами и соперниками по дерби (обычно называют команды конкретно), не играть на выезде непосредственно перед еврокубковыми матчами и т. д. Такие просьбы нетрудно удовлетворить в первоначальном варианте календаря, но «дождевые» и прочие непредвиденные переносы могут все поменять.
– Вы могли бы написать российский календарь?
– Боюсь, нет. Огромная страна, не знакомая мне инфраструктура, да и с футбольной культурой вашей страны я не особенно знаком. А без таких знаний невозможно написать календарь. Впрочем, пару раз ко мне за консультацией обращались составители календарей других стран. Чаще всего по основным, теоретическим вопросам. На практике же на календарь влияют тысячи нюансов, и их нужно знать.
– А за какой клуб вы болеете?
– Намекаете на предвзятость календаря? (Смеется.) Уверяю вас, составить предвзятый календарь с целью дать преимущество какому-то клубу нетрудно, но один проливной дождь может превратить такое расписание из «удобного» в ужасное. К тому же мою работу перепроверяют так часто и скрупулезно, что я, даже если бы хотел, не мог бы «помочь» любимой команде.
– У нас в стране клубам присваиваются номера, а потом идет компьютерная жеребьевка. Это правильный принцип?
– Ну так одни клубы могут благодаря жребию получить более благоприятный календарь. Это, конечно, условное преимущество, но весь календарь нельзя доверять жребию. А вдруг все московские дерби попадут на один день и совпадут с концертом рок-звезды, национальным праздником или траурным днем? Нет, компьютер в деле составления календаря – всего лишь технический помощник. А сам календарь – не что иное, как один компромисс между большим количеством человеческих интересов. Это должны понимать все.
Лондон
А КАК У НАС?
Игорь МЕЩАНЧУК,
спортивный директор РФПЛ:
– В российской премьер-лиге за составление календаря отвечали Борис Бобров, Юрий Кабан, Роман Леонтьев, а с этого года – я. Первоначально при составлении календаря чемпионата России руководствуюсь календарем международных матчей. Потом определяю даты проведения футбольных туров. Далее проводится жеребьевка с участием клубов премьер-лиги, где согласно таблице Бергера получаем календарь турнира. Такая жеребьевка в России проходит четвертый год.
– А вот англичане свой календарь на три четверти пишут вручную…
– Самое сложное – ручная работа, а именно: согласование проекта календаря с учетом пожеланий клубов, МВД России, ГУВД Москвы и Московской области, интересов телевидения. До утверждения календаря клубы премьер-лиги получают его на согласование. В этом году первоначальный вариант был поправлен несколько раз. Например, за три дня до утверждения календаря его срочно пришлось переделывать под «Аланию», вошедшую в премьер-лигу вместо «Москвы».
– Но как бы ни составлялся календарь нашего чемпионата, каждый сезон случаются переносы, связанные с участием российских клубов в еврокубках.
– Согласно регламенту чемпионата российские клубы, участвующие в еврокубках, вправе изменить дату проведения матча в рамках тура. Но регламентом предусмотрены и форс-мажорные обстоятельства.
– Почему в Англии матчи переносятся реже, чем в России?
– Погода может внести коррективы всегда. У них регламент проведения соревнований в три раза толще нашего, и в нем все прописано досконально. Я дважды ездил в Английскую премьер-лигу обмениваться опытом. Поверьте, у педантичных англичан есть чему поучиться.
Можно еще методом грубой силы. Случайно выбирая пары и проверяя, что они еще не играли.
Т.е. цикл по турам. Выбираем пару. Упорядочиваем ее по номеру команд. Смотрим (в хэше), если их нет там, то добавляем в хэш, в расписание и уменьшаем счетчик игр в туре (его начальное значение известно). Как счетчик обнулится переходим к новому туру.
Выбор пар наверное можно оптимизировать, чтобы поменьше вычислять случайные числа.
UPDATE
Другой вариант просто посчитать по турам. Я сделал на C. Судя по результатам работы алгоритм не оптимален для количества команд не равным степени 2-х. Но он работает
/*
avp 2012
Таблица чемпионата (один круг)
n команд (аргумент командной строки)
Составление расписания по турам
Количество туров вычисляется в программе
В stdout выводится список туров с парами команд
и квалратная таблица номеров туров для команд
*/
#include <stdio.h>
#include <stdlib.h>
struct cmd { // данные каждой команды
int ic, // номер команды (с нуля)
ng; // количество уже проведенных игр (init 0)
};
/*
Сортировать команды по возрастанию проведенных игр
(у кого меньше в начало списка)
n - размер списка команд
*/
void
sort (struct cmd a[], // список команд
int n)
{
int i, j;
for (i = 1; i < n; i++) {
struct cmd tt = a[i];
for (j = i; j > 0; j--) {
if (a[j].ng >= a[j-1].ng)
break;
a[j] = a[j-1];
}
if (j < i)
a[j] = tt;
}
}
main (int ac, char *av[])
{
int n = 10; // количество команд в чемпионате
if (ac > 1)
if ((n = atoi(av[1])) < 2)
n = 10;
int game[n][n]; // в каком туре играют j,k (туры с 1, номера команд с 0)
int tot = (n*(n-1))/2; // общее количество игр в круге
int cal[tot][n]; // с кем в туре i играет команда j (все индексы с 0)
int i,j,k, jc, kc, // разные индексы
ng, // количество уже проведенных игр в круге
nt; // количество туров (вычисляетя в ходе составления расписания)
// инициализация таблицы игр в круге
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
game[i][j] = 0; // здесь будет в каком туре играют команды i,j
}
game[i][i] = -1;
}
// инициализация таблицы по турам (количество туров с большим запасом)
for (i = 0; i < tot; i++)
for (j = 0; j < n; j++)
cal[i][j] = 0; /* здесь будет с какой командой (номер с 1)
в туре i (индекс с 0) играет команда j (индекс с 0)
*/
struct cmd a[n]; // список команд
for (i = 0; i < n; i++) {
a[i].ic = i;
a[i].ng = 0;
}
// собственно вычисления
for (i = ng = 0; ng < tot; i++) { // увеличиваем туры (i) пока не сыграли
// все матчи круга (ng)
sort(a,n); // это для равномерности (?) по турам
for (j = 0; j < n; j++) { // перебираем команды из списка
jc = a[j].ic;
if (cal[i][jc])
continue; // уже играла в этом туре
for (k = 0; k < n; k++) { // перебираем команды из списка
kc = a[k].ic;
if (kc == jc)
continue; // сама с собой
if (cal[i][kc] || game[jc][kc])
continue; // kc уже играла в туре или играла раньше с jc
/*
kc и jc еще не играли. Пусть сыграют в этом туре
увеличим количество проведенных игр и заполним таблицы
*/
ng++;
a[jc].ng++;
a[kc].ng++;
cal[i][kc] = jc+1;
cal[i][jc] = kc+1;
game[jc][kc] = i+1;
game[kc][jc] = i+1;
break;
}
}
}
nt = i; // это сколько туров получилось.
// печать игр по турам
printf ("ntours %dn",nt);
for (i = 0; i < nt; i++) {
printf ("tour %dn",i+1);
int t[n];
for (j = 0; j < n; j++)
t[j] = 0;
for (j = 0; j < n; j++) {
if (k = cal[i][j]) {
if (!t[k-1]) {
// printf ("%2d:%2d ",j+1,k);
printf (" %c : %c ",'A'+j,'A'+k-1);
t[j] = t[k-1] = 1;
}
}
}
printf ("n");
}
// печать квадратной таблицы туров для команд
printf ("ntours tablen");
printf (" ");
for (i = 0; i < n; i++)
// printf ("%2d ",i+1);
printf (" %c ",'A'+i);
printf ("n");
for (i = 0; i < n; i++) {
// printf (" %2d ",i+1);
printf (" %c ",'A'+i);
for (j = 0; j < n; j++) {
printf ("%2d ",game[i][j]);
}
printf ("n");
}
printf ("n");
}
Уважаемый @namak, Вы уж извините меня за программу на Си. Я понимаю, что Вы спрашивали PHP с SQL, но Си я владею значительно лучше, а алгоритм надеюсь будет понятен.
Алгоритм (операторы) собственно находится между комментариями
// собственно вычисления
и
// печать игр по турам
UPDATE 2
Функция перемешивающая команды (вместо sort())
void
shuffle (struct cmd a[], int n)
{
int i, j;
static int first = 1;
if (first) {
first = 0;
srand(time(0));
}
for (i = 0; i < n; i++) {
struct cmd tt;
j = rand()%n;
tt = a[j];
a[j] = a[i];
a[i] = tt;
}
}