Планирование соревнований

Question

Мне нужно составить расписание спортивного мероприятия.

Имеются 30 команд. Каждая команда должна сыграть 8 матчей. Это означает, что каждая команда не может снова конкурировать со всеми другими командами, но мне нужно избегать того, чтобы две команды неоднократно соревновались друг с другом.

Моя идея состояла в том, чтобы сгенерировать все возможные совпадения (для 30 команд: (30*29)/2 = 435 matches) и выбрать из этого списка 120 совпадений (8 совпадений для каждой команды: 8 * 30/2 = 120 matches).

Это то место, где мне тяжело: как я могу выбрать эти 120 матчей? Я попробовал несколько простых решений (возьмите первое совпадение списка, затем последнее и т. Д.), Но они, похоже, не работают с 30 командами. Я также пытался создать всю возможную комбинацию совпадений и найти, какой из них работает, но с 30 командами, это слишком много расчетного времени.

Есть ли существующий алгоритм, который я мог бы реализовать?

UPDATE

Что мне нужно, чтобы произвести это простой график, без исключения. Каждая команда играет 8 матчей, и все. В конце дня не будет один победитель.

У каждой команды будет свое расписание, и это расписание не изменится, если они выиграют или проиграют. Планирование выполняется на весь день и является неизменным.

UPDATE 2

Сначала я не хотел ставить слишком много ограничений на мой вопрос, но мне кажется, что без каких-либо ограничений (кроме каждой команды не конкурируя более чем один раз друг с другом) , это всего лишь случай случайного выбора 8 матчей для каждой команды.

Так вот еще некоторые детали:

Во время этого спортивного события, есть 6 Differents спорта (футбол, гандбол, баскетбол, и так далее). Это означает, что есть 6 одновременных матчей. Новый раунд запускается каждые 15 минут.

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

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

Команда не может играть в два матча подряд.

Answer 1

Уверены, что вы не смогли получить 32 команды :-)?

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

С 30 командами вы могли бы сыграть 2 команды в товарищеском матче и сыграть в первом раунде. Но организация становится намного сложнее.

Answer 2

Я не знаю существующую реализацию, но здесь является возможным решением для вас:

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

Теперь возьмите оставшиеся три команды, по одному для каждой группы.

Изменить некоторые игры каждой команды:

1-2 -> 1-10, 2-10 
3-4 -> 3-10, 4-10 
5-6 -> 5-10, 6-10 
7-8 -> 7-10, 8-10 

Answer 3

Вы можете посмотреть в какое-то уже известном совпадение подходов:

Э.Г. Swiss Chess system

Edit:

После прочтения ваших требований еще раз - что каждая команда должна играть каждую другую команду только один раз, и что победитель не обязательно должен быть решен. Кажется, что одна система Round Robin будет делать то, что вы хотите. Вы можете просто отказаться от дополнительных матчей выше 8, которые вам нужны.

Answer 4

Это довольно просто, просто объединиться команда i с i-4, i-3, i-2, i-1, i+1, i+2, i+3, i+4. Это можно сделать, используя приведенный ниже алгоритм.

import java.util.*; 

public class Test { 

    public static void main(String[] args) { 

     int TEAMS = 30, MATCHES = 8; 
     int[] matchCount = new int[TEAMS]; // for a sanity check. 
     List<Match> matches = new ArrayList<Match>(); 

     for (int team1 = 0; team1 < TEAMS; team1++) 
      for (int team2 = team1 + 1; team2 <= team1 + MATCHES/2; team2++) { 
       matches.add(new Match(team1, team2 % TEAMS)); 

       // Just for a sanity check: 
       matchCount[team1]++; 
       matchCount[team2 % TEAMS]++; 
      } 

     System.out.println(matches); 

     // Sanity check: 
     System.out.println(matches.size()); 
     System.out.println(Arrays.toString(matchCount)); 
    } 

    static class Match { 
     int team1, team2; 
     public Match(int team1, int team2) { 
      this.team1 = team1; 
      this.team2 = team2; 
     } 
     public String toString() { 
      return team1 + " vs " + team2; 
     } 
    } 
} 

Выход:

[0 vs 1, 0 vs 2, 0 vs 3, 0 vs 4, 1 vs 2, 1 vs 3, 1 vs 4, 1 vs 5, 2 vs 3, 2 vs 4, 2 vs 5, 2 vs 6, 3 vs 4, 3 vs 5, 3 vs 6, 3 vs 7, 4 vs 5, 4 vs 6, 4 vs 7, 4 vs 8, 5 vs 6, 5 vs 7, 5 vs 8, 5 vs 9, 6 vs 7, 6 vs 8, 6 vs 9, 6 vs 10, 7 vs 8, 7 vs 9, 7 vs 10, 7 vs 11, 8 vs 9, 8 vs 10, 8 vs 11, 8 vs 12, 9 vs 10, 9 vs 11, 9 vs 12, 9 vs 13, 10 vs 11, 10 vs 12, 10 vs 13, 10 vs 14, 11 vs 12, 11 vs 13, 11 vs 14, 11 vs 15, 12 vs 13, 12 vs 14, 12 vs 15, 12 vs 16, 13 vs 14, 13 vs 15, 13 vs 16, 13 vs 17, 14 vs 15, 14 vs 16, 14 vs 17, 14 vs 18, 15 vs 16, 15 vs 17, 15 vs 18, 15 vs 19, 16 vs 17, 16 vs 18, 16 vs 19, 16 vs 20, 17 vs 18, 17 vs 19, 17 vs 20, 17 vs 21, 18 vs 19, 18 vs 20, 18 vs 21, 18 vs 22, 19 vs 20, 19 vs 21, 19 vs 22, 19 vs 23, 20 vs 21, 20 vs 22, 20 vs 23, 20 vs 24, 21 vs 22, 21 vs 23, 21 vs 24, 21 vs 25, 22 vs 23, 22 vs 24, 22 vs 25, 22 vs 26, 23 vs 24, 23 vs 25, 23 vs 26, 23 vs 27, 24 vs 25, 24 vs 26, 24 vs 27, 24 vs 28, 25 vs 26, 25 vs 27, 25 vs 28, 25 vs 29, 26 vs 27, 26 vs 28, 26 vs 29, 26 vs 0, 27 vs 28, 27 vs 29, 27 vs 0, 27 vs 1, 28 vs 29, 28 vs 0, 28 vs 1, 28 vs 2, 29 vs 0, 29 vs 1, 29 vs 2, 29 vs 3] 
120 
[8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8] 

Если вы хотите более рандомизированное настройки, вы можете просто присвоить случайное число в диапазоне от 1 до 30 в каждой команде.

---

Update Чтобы справиться с ограничениями добавленных Пусть матч я быть спорт я моды 6.

Answer 5

Брокерский алгоритм может работать. Как ни странно, я не могу найти хорошее описание в сети, поэтому я попытаюсь объяснить систему.

Фактически каждая команда задавала друг другу команду за очко за матч и выбирала самую высокую оценку. Это повторяется для каждой команды и соответствует. Полученный график сохраняется и вычисляется общий балл. Затем с разными начальными точками (т. Е. Вы можете просто упорядочить порядок команды) это делается снова, и если общий балл выше, это расписание выбирается вместо этого. Вы повторяете это до тех пор, пока не найдете график с высокой степенью достаточности или после определенного количества попыток.

Общая оценка может быть рассчитана по расстоянию, пройденному каждой командой, чем меньше число, тем лучше. Очевидно, вы не выбираете совпадения, которые нарушают ваши правила (слишком много матчей аналогичного типа, одни и те же команды снова играют друг с другом).

Скоринг может пойти что-то вроде этого:

1. Если же место для команды: 100 баллов (то есть, если для обоих = 200).
2. Для поездок между местами оценка определяется для обеих команд в зависимости от длины, то есть A -> B и B -> A 50 баллов (они близки) A -> C и C -> A 30 баллов (не так близко) B -> C и C -> B 0 баллов (путешествие, которое мы хотим сделать как можно меньше).
3. Если команда еще не сыграла в этом спорте: 100 очков.
4. Если команда сыграла этот вид спорта один раз: 50 очков.

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

Answer 6

Если вы хотите простой алгоритм, который будет создавать расписание, когда команды не играют друг против друга более одного раза, что не сложно с заданными параметрами.

Вот пример для 10 команд и 5 раундов, решение показано как массив, где, если значение расписания [i] [j] равно нулю, команды не играют вместе, а если это число то он показывает, в каком раунде они играют вместе.

1 2 3 4 5 6 7 8 9 10 
1 [0, 5, 0, 4, 0, 3, 0, 2, 0, 1] 
2 [5, 0, 4, 0, 3, 0, 2, 0, 1, 0] 
3 [0, 4, 0, 3, 0, 2, 0, 1, 0, 5] 
4 [4, 0, 3, 0, 2, 0, 1, 0, 5, 0] 
5 [0, 3, 0, 2, 0, 1, 0, 5, 0, 4] 
6 [3, 0, 2, 0, 1, 0, 5, 0, 4, 0] 
7 [0, 2, 0, 1, 0, 5, 0, 4, 0, 3] 
8 [2, 0, 1, 0, 5, 0, 4, 0, 3, 0] 
9 [0, 1, 0, 5, 0, 4, 0, 3, 0, 2] 
10[1, 0, 5, 0, 4, 0, 3, 0, 2, 0] 

Так из этой таблицы в первом раунде команды (1, 10), (2, 9), (3, 8), (4, 7), (5, 6) играть, во втором круглые команды (1, 8), (2, 7), (3, 6) ... и т.д.

Для создания этой таблицы алгоритм довольно тривиально, здесь есть некоторые питона код:

#!/bin/env python 

def simpleNRooks(size, rounds, schedule): 
    ''' Place n rooks on board so that they don't hit each other in each round, 
     nor reuse the spots from previous rounds ''' 
    for i in range(size): 
     for j in range(rounds): 
      if size-j*2-i-1 < 0: 
       schedule[i][2*size-j*2-i-1] = j + 1 
      else: 
       schedule[i][size-j*2-i-1] = j + 1 

# parameters 
teams = 10 
matches = 5 

# prepare the schedule, 0's designate free space 
schedule = [[0 for i in range(teams)] for j in range(teams)] 

simpleNRooks(teams, matches, schedule) 

print 'Final schedule' 
for i in range(teams): 
    print schedule[i] 

Если вы хотите получить другую структуру данных (например, список пар по раундам), вы можете использовать тот же принцип, но изменять петли.

Answer 7

Я добавляю отдельный ответ, учитывая новые ограничения, поскольку я думаю, что это яснее, чем добавление к моему старому ответу.

1. расколоть 30 команд на 5 групп, каждая из 6 команд: A B C D E

2. Для первого периода Группы A и B игр.

3. Тогда C & D, Е & А, В & С, D & Е, в течение следующих 4 пятнадцати минутных сегментов.

Итак, в конце 5 * 15 минут: каждая команда сыграла дважды, по крайней мере, с одним периодом отдыха между ними.

Иметь 20 периодов и каждый сыграл 8 раз.

Необходимо, чтобы команда в группе B, например, могла играть против 8 других команд из 17 других команд в группах A, B & C.

Например, сыграйте команды против соответствующих команд B, а затем команды B против совпадающих команд C, затем обратные списки, затем в группах, затем MOD 2, MOD 3 между группами и внутри групп.

Это просто сводит к минимуму время в пути и гарантирует, что каждая команда играет в каждый тип игры. Но разрешите ли это для одной группы, и вы можете применить одно и то же решение ко всем другим?