Обратите внимание, что каждая команда играет 3 других за матч, поэтому для всех 15 команд требуется не менее 5 матчей. Таким образом, мы надеемся, что есть решение для 20 матчей, где каждая команда играет 5 матчей и играет каждую команду ровно один раз.
С 16 командами можно построить решение вручную следующим образом ...
- Разделите 20 матчей на 5 раундов
- Количество команд от 1 до 16
- Для каждого матча по очереди, для каждого из 4 мест в этом матче, выделите первую команду, которая
- все еще доступен для игры в этом раунде
- еще не играл ни одной из команд, уже назначенных на этот матч
Вы можете несколько сузить поиск доступных команд, отметив, что в каждом матче должна содержаться ровно одна команда из каждого матча предыдущего раунда, поэтому для места n нужно учитывать только команды, сыгравшие матч n в предыдущем раунде. 1019 *
Если мы хотим 24 матча, то в шестом раунде будет достаточно произвольного выбора матчей, чтобы соответствовать исходным требованиям. Однако, чтобы гарантировать, что никакие точные совпадения не повторяются, мы можем переключать пары команд между матчами в каком-то предыдущем раунде. То есть, если {1,2,3,4} и {5,6,7,8} были совпадениями в каком-то раунде, то в шестом раунде мы получим {1,2,7,8} и {3,4 , 5,6}. Поскольку 1 и 2 играли друг с другом ровно один раз в раундах 1-5, в матче {1,2,3,4} мы, конечно, еще не играли в матче {1,2,7,8}.
Выбор структур данных для эффективной реализации оставлен читателю в качестве упражнения.