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

Question

Я работаю в Ruby, но я думаю, что этот вопрос лучше всего задавать независимо от языка. Можно предположить, что у нас есть доступ к основным функциям списка / массива, а также к генератору «случайных» чисел. Вот что я хотел бы сделать:

Учитывая коллекцию n команд, с n чётными,

1. Произвольно связывает каждую команду с противником, так что каждая команда является частью ровно одной пары. Назовите это ROUND 1.
2. Произвольно генерирует n-2 последующие раунды (ROUND 2 - ROUND n-1), такие что:
   • Каждый раунд имеет то же свойство, что и первый (каждая команда член одной пары) и
   • После всех раундов каждая команда сталкивалась с любой другой командой ровно один раз.

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

Answer 1

Я верю Вы описываете Турнир с круговым турниром . Страница википедии дает алгоритм.

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

Answer 2

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

http://www.devenezia.com/downloads/round-robin/

В дополнение к алгоритму у него есть несколько полезных ссылок на другие аспекты планирования турниров (балансирование домашних и выездных игр, а также ротация команд по полям / кортам).

Обратите внимание, что вы не обязательно хотите "случайный" порядок для пар во всех случаях. Например, если вы запланировали круговую футбольную лигу на 8 игр, в которых было только 6 команд, то каждая команда должна будет сыграть две другие команды дважды. Если вы хотите, чтобы сезон был более приятным для всех, вам нужно начать беспокоиться о посеве, чтобы у вас не было двух лучших команд, которые разбили две слабейшие команды в последних двух играх. Вам лучше организовать дополнительные игры в паре с командами с одинаковой силой / затравкой.

Answer 3

Ну, не уверен, что это самый эффективный алгоритм, но:

1. Произвольно назначить N команд в два списка одинаковой длины n / 2 (List1, List2)
2. Начиная с i = 0:
3. Создание пар: List1 [i], List2 [i] = командная пара

4. Повторите для i = 1-> (n / 2-1)

   Для раундов 2-> n / 2-1:

5. Поверните List2, чтобы первая команда в List2 оказалась в конце.
6. Повторяйте шаги со 2 по 5, пока List2 не будет один раз зациклен.

Answer 4

На основании информации, которую я нашел по ссылке Маника , я выбрал следующее:

1. Простой алгоритм циклического перебора, который

   а. Начинается со спаривания, достигаемого zip [0,...,(n-1)/2] и [(n-1)/2 + 1,..., n-1]. (Таким образом, если n==10, у нас есть 0 в паре с 5, 1 с 6 и т. Д.)

   б. Вращает все команды, кроме одной, n-2 раза по часовой стрелке, пока все команды не сыграют друг с другом. (Таким образом, во втором раунде мы соединяем 1 с 6, 5 с 7 и т. Д.)

2. Произвольно присваивает одну из [0,..., n-1] каждой из команд.