Алгоритм составления расписания спортивных матчей

Сегодня один форумчанин обратился на форум с просьбой о помощи в составлении календаря игр для футбола. Я решил помочь и сделал простой скрипт, который составит расписание матчей. Данный скрипт годен только для турниров, в которых будет участвовать четное количество команд. Алгоритм довольно прост, и я его объясню под катом и дам рабочий скрипт.

Алгоритм создания расписания игр для четного количества команд по круговой системе очень прост.

Круговая система это когда каждая команда играет со всеми командами.

Теория. 

Допустим мы назначим каждой команде свой индивидуальный порядковый номер. К примеру построим расписание для турнира из 8 команд.

Пускай количество команд будет N=8.

N=2*K, где К, как вы догадались из формулы, это половина команд.

Итак, начнем. Для круговой системы запишем все номера команд от 1 до K слева сверху вниз, а с права снизу вверх разместим номера от К+1 до N.

Таким образом у нас получится такая вот табличка:

1	8
2	7
3	6
4	5

Таким образом в 1 туре у нас играет 1 и 8, 2 и 7, 3 и 6, 4 и 5 команды.

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

Таким образом мы получим во втором туре такой список матчей:

1	2
3	8
4	7
5	6

Как видно, все команды сместились против часовой стрелки, 2 команда стала на место последней, последняя на место предпоследней и т.д.

Соответственно с каждым туром у нас будет такое же смещение, например в третьем туре на место 3 команды станет 4, а на место 2 команды станет третья и т.д.

1	3
4	2
5	8
6	7

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

Количество туров будет равно N-1

PHP реализация. 

< ?
# массив команд
$team = array('1'=>'1',
        '2',
        '3',
        '4',
        '5',
        '6',
        '7',
        '8',
        '9',
        '10',
        '11',
        '12',
        '13',
        '14',
        '15',
        '16',
        '17',
        '18',
        '19',
        '20');
$all_team = count($team);
$k = $all_team/2; 

# 1 тур
echo '1 тур ';
for($i=1;$i< =$k;$i++)
{
    echo $team[$i].' - '.$team[($all_team-$i+1)].'';
} 

# Следующие туры
for($i=2;$i< $all_team;$i++)
{
echo $i.' тур '; 

$team2 = $team[2]; 

for($y=2;$y< $all_team;$y++)
{
    $team[$y] = $team[$y+1];
}
$team[$all_team] = $team2; 

for($j=1;$j<=$k;$j++)
{
    echo $team[$j].' - '.$team[($all_team-$j+1)].'';
} 

}
?>

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

На обычном хостинге список матчей для 20 команд сгенерировался за 0.0003 сек.

 

Метки: php жеребьевка команд, Аглоритм жеребьевки, круговая система жеребьевки, расписание игр

4 комментария к “Алгоритм составления расписания спортивных матчей”

1. 1
   DiB
   9 августа 2011 в 00:57

   Спасибо за такой простой алгоритм…
   Увеличив цикл
   # Следующие туры
   for($i=2;$i< $all_team*2-1;$i++)

   и добавив проверку на четность тура
   if ($i%2!=0){
   echo $team[$j].' – '.$team[($all_team-$j+1)].'’;
   }else{
   echo $team[($all_team-$j+1)].’ – ‘.$team[$j].";
   }
   можно сделать двухкруговой турнир со своим полем…

2. 2
   Дмитрий
   9 февраля 2012 в 13:21

   Ох спасибо! вот прям очень пригодилось!

3. 3
   Кирилл
   20 февраля 2012 в 18:51

   так тот же алгоритм подойдёт и для нечётного количества команд!!!!
   достаточно добавить "неиграющую" команду.
   То есть, если 2н-1 команда, провест турнир для 2н команда, считаю, что команда играющая с 2н-ой отдыхает в этом туре!!

   но вот в чём пробелмка: меня интерисует тот же вопрос, но что бы сетка была "случайной", то есть матчи были б "более в разброс". Просто такая сетка считается плохим тоном при составлении календарей(

4. 4
   mr.Z
   21 февраля 2012 в 05:16

   Кирилл, да, можно и дописать под нечетное количество команд, тогда 1 команда будет "отдыхать" во время матчей других.
   На счет "случайной" сетки не понял на выходе вы получаете массив со всеми матчами, вы можете оперировать с ними, как вам угодно