Для решения одной, как я считаю, амбициозной задачи, связанной с проведением футбольного турнира, мне необходимо было использовать процедуру формирования соревновательных пар, т.е. провести жеребьевку. Но произвести ее нужно не обычным «человеческим» способом, а автоматизировано. Поискав готовые решения аналогичной задачи, нашел только формирование корзин участников при наличии сеянных и несеянных команд (Пример), что меня не устроило и не решало поставленной задачи. В итоге проанализировав процедуру обычной однокруговой жеребьевки, сформировал следующий алгоритм и условия:
Входные условия жеребьевки:
- Имеется N команд – участников.
- Каждая команда за первый круг сыграет N-1 матчей.
- Команда N ни в каком из туров не может сыграть сама с собой.
- В каждом туре соперники образуют уникальные, не повторяющиеся ранее пары.
- Если в каком-то из туров команда N играет с командой M, то соответственно в этом же туре команда M играет с командой N.
Сопоставив процесс формирования случайных пар соперников процедуре заполнения двумерного массива DrawTable[i, j] случайными величинами, получил следующее (язык C#, .Net 4.0):
1. Выбираем команду N из определенного диапазона (в данном варианте, они упорядочены по текущему месту в чемпионате):
string[] teams = new string[] {"ЦСКА", "Анжи", "Зенит", "Кубань", "Терек", "Спартак", "Рубин", "Локомотив", "Динамо", "Краснодар", "Ростов", "Амкар", "Волга НН", "Крылья Советов", "Алания", "Мордовия"};
2. Проверяем, заполнена ли ячейка DrawTable[i, N]. Для этого изначально присвоим каждому элементу массива любое отрицательное число, например {-1}:
drawtable[i, j]=-1; if (drawtable[i, j] < 0)
{…}3. Начинаем процедуру формирования случайных соперников для команды N: TableDraw[i, N]=Random=Mi контролируя и исполняя входные условия 3-5:
int pair = generator.Next(1000, 1000000)%teams.Length;
Изначально, использовался
int pair = generator.Next(0, teams.Length)
однако разброс генерируемых чисел в такой интерпретации недостаточный и не позволял построить массив.
Изначально производится проверка условия 3:
if (pair != j)
Далее вертикальная
if (pair != drawtable[k, j])
и горизонтальные проверки
if (pair != drawtable[i, k])
условия 4.
Если выполняются условия 3, 4 то формируется пара:
drawtable[i, j] = pair; drawtable[i, pair] = j;
Вышеописанные операции производятся для каждого участника в каждом туре:
for (int i = 0; i < teams.Length - 1; i++) { for (int j = 0; j < teams.Length; j++) { } }
В результате формируется соревновательная таблица следующего вида:
Если по причине некорректного формирования массива, возникает, так называемая «Рыба» (а она возникает) -ситуация, когда нет решения, необходимо откатить произведенные итерации, при условии, чем больше размеры массива, тем больше количество откатываемых итераций. В данном случае откатывается последняя итерация:
fail++; if (fail > teams.Length) {for (int k = 0; k < teams.Length; k++){drawtable[i, k] = -1;} fail = 0; j = -1;}
Таким нехитрым образом, можно сформировать пары участников не применяя шарики, кубышки и т.п., и что самое главное, использовать эту процедуру для более обширной задачи формирования общего календаря соревнований, которая находится в стадии проектирования.
Автор: kimssster
