Жеребьевка — нажатием кнопки

в 16:11, , рубрики: алгоритм, Алгоритмы, метки: ,

Для решения одной, как я считаю, амбициозной задачи, связанной с проведением футбольного турнира, мне необходимо было использовать процедуру формирования соревновательных пар, т.е. провести жеребьевку. Но произвести ее нужно не обычным «человеческим» способом, а автоматизировано. Поискав готовые решения аналогичной задачи, нашел только формирование корзин участников при наличии сеянных и несеянных команд (Пример), что меня не устроило и не решало поставленной задачи. В итоге проанализировав процедуру обычной однокруговой жеребьевки, сформировал следующий алгоритм и условия:
Входные условия жеребьевки:

  1. Имеется N команд – участников.
  2. Каждая команда за первый круг сыграет N-1 матчей.
  3. Команда N ни в каком из туров не может сыграть сама с собой.
  4. В каждом туре соперники образуют уникальные, не повторяющиеся ранее пары.
  5. Если в каком-то из туров команда 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++) { } }

В результате формируется соревновательная таблица следующего вида:
image
Если по причине некорректного формирования массива, возникает, так называемая «Рыба» (а она возникает) -ситуация, когда нет решения, необходимо откатить произведенные итерации, при условии, чем больше размеры массива, тем больше количество откатываемых итераций. В данном случае откатывается последняя итерация:

fail++; if (fail > teams.Length) {for (int k = 0; k < teams.Length; k++){drawtable[i, k] = -1;} fail = 0; j = -1;}

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

Автор: kimssster

Источник

Поделиться

* - обязательные к заполнению поля