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

Ответ 1

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

например. Швейцарская шахматная система

Edit:

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

Ответ 2

Это довольно просто, просто объедините команду 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 каждой команде.

Обновить Чтобы справиться с вашими дополнительными ограничениями: Позвольте мне соответствовать спорту я mod 6.

Ответ 3

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

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

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

Ответ 4

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

Сделайте три группы из 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

Ответ 5

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

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

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

Скоринг может выглядеть примерно так:

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

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

Ответ 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)... и т.д.

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

#!/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 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]

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

Ответ 7

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

• Разделите 30 команд на 5 групп, каждая из 6 команд: A B C D E

• В первый период игры группы A и B.

• Затем C & D, E & A, B & C, D & E, в течение следующих 4 пятнадцатиминутных сегментов.

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

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

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

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

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